数据结构|数据结构—线性表数据结构|链表|c语言|线性表

线性表的操作

（一）单链表的操作

（1）用随机函数生成8个3位整数（100~999），把这些整数存于单链表中；
（2）输出单链表的内容；
（3）读入一个整数，查看该整数是否在表中，若在，输出其位置（首位置为1）；
（4）读入一个整数，以及要插入的位置，把该整数插入到单链表中，输出单链表的内容（要求判断输入的位置是否合理）；
（5）读入一个整数，若该整数在单链表里，删除该整数，输出单链表的内容；
【数据结构|数据结构—线性表】（6）把链单表的内容翻转，输出单链表的内容。

//链式存储的线性表 /* 李子木 */#include #include #include #include #include typedef int ElementType; // ElementType 可定义为任意类型 typedef struct LNode *List; struct LNode{ ElementType Data; //数据域 List Next; // 下一个链表的地址 }; List L; List MakeEmpty(); //初始化链表 int Length(List L); // 以遍历链表的方法求链表长度 List FindKth(int K,List L); // 按序号查找 int Find(ElementType X,List L); // 按值查找 List Insert(ElementType X,int i,List L); //将 X 插入到第 i-1(i>0) 个结点之后 List Delete(ElementType X,List L); // 删除第 i(i>0) 个结点 void Print(List L); // 输出链表元素 List biu1(List L); //内容反转（迭代） List biu2(List L); //内容反转（递归）// 初始化链表 List MakeEmpty(){ List L = (List)malloc(sizeof(struct LNode)); List p = (List)malloc(sizeof(struct LNode)); L = p; srand((unsigned)time(NULL)); for(int i = 0; i < 8; i++){ p->Data=https://www.it610.com/article/rand()%900+100; if(i<7){ p->Next=(List)malloc(sizeof(struct LNode)); p=p->Next; } } p->Next=NULL; return L; }//求表长 int Length(List L){ List p = L; int len=0; while(p){// 当 p 不为空 p = p->Next; len++; } return len; } // 按序查找 List FindKth(int K,List L){ List p = L; int i = 1; //从 1 开始 while(p && iNext; i++; } if(i == K)// 找到了 return p; else// 未找到 return NULL; } // 按值查找 int Find(ElementType X,List L){ List p = L; int len=1; while(p && p->Data!=X){ p=p->Next; len++; } if(p==NULL) return -1; return len; } /* 插入 1. 用 s 指向一个新的结点 2. 用 p 指向链表的第 i-1 个结点 3. s->Next = p->Next，将 s 的下一个结点指向 p 的下一个结点 4. p->Next = s，将 p 的下一结点改为 s*/ List Insert(ElementType X,int i,List L){ List p,s; if(i == 1){// 新结点插入在表头 s = (List)malloc(sizeof(struct LNode)); if(s==NULL){ printf("分配内存错误！"); return L; } s->Data = https://www.it610.com/article/X; s->Next = L; return s; //插入的结点为头结点 } p = FindKth(i-1,L); // 找到第 i-1 个结点 if(!p){// 第 i-1 个结点不存在 printf("结点错误"); return NULL; }else{ s = (List)malloc(sizeof(struct LNode)); if(s==NULL){ printf("分配内存错误！"); return L; } s->Data = https://www.it610.com/article/X; s->Next = p->Next; //将 s 的下一个结点指向 p 的下一个结点 p->Next = s; // 将 p 的下一结点改为 s return L; } }/* 删除 1. 用 p 指向链表的第 i-1 个结点 2. 用 s 指向要被删除的的第 i 个结点 3. p->Next = s->Next，p 指针指向 s 后面 4. free(s)，释放空间 */ List Delete(ElementType X,List L){ List p,s; int k; k=Find(X,L); if(k==1){//如果要删除头结点 s = L; if(L)// 如果不为空 L = L->Next; else return NULL; free(s); // 释放被删除结点 return L; } p = FindKth(k-1,L); // 查找第 i-1 个结点 if(!p || !(p->Next)){// 第 i-1 个或第 i 个结点不存在 printf("结点错误"); return NULL; }else{ s = p->Next; // s 指向第 i 个结点 p->Next = s->Next; //从链表删除 free(s); // 释放被删除结点 return L; } }// 输出链表元素 void Print(List L){ List t; int flag = 1; printf("当前链表为："); for(t = L; t; t =t->Next){ printf("%d",t->Data); flag = 0; } if(flag) printf("NULL"); printf("\n"); }//内容反转（迭代） List biu1(List L) { List p,s; p = (List)malloc(sizeof(struct LNode)); p = L; if (L == NULL || L->Next == NULL) { return L; } s = NULL; while (p != NULL) { List tmp = p->Next; //暂存p后面一个元素 p->Next = s; s = p; //p->Next指向前一个元素 p = tmp; //p指向原始链表的下一个元素 } return s; }//内容反转（递归） List biu2(List L) { if (L == NULL || L->Next == NULL) { return L; } List s = biu2(L->Next); L->Next->Next = L; L->Next = NULL; return s; }int main() { List L; L = MakeEmpty(); int x, k; Print(L); printf("请输入一个整数："); scanf("%d", &x); if (Find(x, L) == -1) { printf("查无此值！\n"); } else { printf("该值所在位置为：%d\n", Find(x, L)); } printf("请输入需要插入的元素值以及插入位置："); scanf("%d%d", &x, &k); L = Insert(x, k, L); Print(L); printf("请输入需要删除的元素："); scanf("%d", &x); L = Delete(x, L); Print(L); system("pause"); //等待用户按任意键，然后返回, 等同于getchar() L = biu1(L); printf("执行链表反转...\n"); system("pause"); Print(L); L = biu2(L); printf("执行链表反转...\n"); system("pause"); Print(L); return 0; }

（二）顺序表的操作

（1）用随机函数生成8个3位整数（100~999），把这些整数存于顺序表中；
（2）输出顺序表的内容；
（3）读入一个整数，查看该整数是否在顺序表中，若在，输出其位置（首位置为1）；
（4）读入一个整数，以及要插入的位置，把该整数插入到顺序表中，输出顺序表的内容（要求判断输入的位置是否合理）；
（5）读入一个整数，若该整数在顺序表里，删除该整数，输出顺序表的内容；
（6）把顺序表的内容翻转，输出顺序表的内容。

//顺序存储的线性表 /* 李子木 */#include #include #include #include #include #define MAXSIZE 100// MAXSIZE 定义为 Data 数组的大小 typedef int ElementType; // ElementType 可定义为任意类型 typedef struct LNode *List; struct LNode{ ElementType Data[MAXSIZE]; int Last; // Last 定义线性表的最后一个元素 }; List L; //访问下标为 i 的元素：L->Data[i] //线性表的长度：L->LastList MakeEmpty(); //初始化顺序表 int Find(ElementType X,List L); //查找 X 第一次出现的下标 void Insert(ElementType X,int i,List L); //在下标为 i 的地方插入 X void Delete(int i,List L); //删除下标为 i 的当前值 ElementType FindS(int i,List L); //返回下标为 i 的当前值 int Length(List L); //返回顺序表的长度可以不用，但不能不会 void biu(List L); //使线性表内内容反转 //初始化 List MakeEmpty(){ List L; L = (List)malloc(sizeof(struct LNode)); L->Last = 0; return L; }// 按值查找 int Find(ElementType X,List L){ int i=1; while(i <= L->Last && L->Data[i] != X) i++; if(L->Last < i)//如果没找到，返回 -1 return -1; else// 找到后返回下标 return i; }// 插入 void Insert(ElementType X,int i,List L){ int j; if(L->Last == MAXSIZE-1){//位置已满 printf("表满"); return; } if(i < 0 || L->Last + 1 < i){//位置越界 printf("位置不合法"); return; } for(j=L->Last; j>=i; j--)// 从后往前依次向后挪一个 L->Data[j+1] = L->Data[j]; L->Data[i] = X; //新元素插入 L->Last++; // Last仍然指向最后元素 return; } //删除 void Delete(ElementType x,List L){ if(L->Last==0){ printf("空表"); return; } int i,j; for(i=1; i<=L->Last; i++){ if(L->Data[i]==x){ for(j=i; jLast; j++)//被删除的元素后面的元素前移 L->Data[j]=L->Data[j+1]; L->Last--; //Last指向最后元素 return; } } printf("未找到该值"); }//按下标查找 ElementType FindS(int i,List L){ if(i < 0 || L->Last < i)return; return L->Data[i]; }//表长 int Length(List L){ return L->Last; }//内容反转 void biu(List L){ int i,t; for(i=1; i<=((L->Last+1)/2); i++){ t=L->Data[i]; L->Data[i]=L->Data[L->Last-i+1]; L->Data[L->Last-i+1]=t; } }int main(){ List L; L=MakeEmpty(); int i,x; srand((unsigned)time(NULL)); //设置种子，使得产生的随机数是可变化的 for(i=1; i<=8; i++){//插入三个随机100-999之间的整数 Insert(rand()%900+100,i,L); } printf("单链表中的内容为："); for(i=1; i<=8; i++)//输出链表中的的内容 printf("%d ",L->Data[i]); printf("\n"); printf("请输入一个整数："); scanf("%d",&x); if(Find(x,L)!=-1) printf("查找值为%d的下标为：%d\n",x,Find(x,L)); if(Find(x,L)==-1) printf("未找到该值\n"); printf("请输入需要插入的整数："); scanf("%d",&x); Insert(x,L->Last+1,L); printf("此时单链表中的内容为："); for(i=1; i<=9; i++) printf("%d ",L->Data[i]); printf("\n"); printf("请输入需要删除的整数："); scanf("%d",&x); Delete(x,L); printf("删除元素后单链表中的内容为："); for(i=1; i<=L->Last; i++) printf("%d ",L->Data[i]); printf("\n"); biu(L); printf("内容反转后链表中内容为："); for(i=1; i<=L->Last; i++) printf("%d ",L->Data[i]); return 0; }