用一段完整的代码来理解线性表各个函数的作用 函数：初始化、查找、插入、删除

此博客已经自用，借鉴时千万不要直接复制粘贴

作业是改PPT上的代码，跟这个貌似不太一样，需注意！

#include <stdio.h> #include <stdlib.h> #include <string.h> using namespace std; #define Init_size 10//线性表储存空间初始分配量 #define add_size 2//线性表储存空间分配增量 #define ElemType int//定义类型，线性表想存字符就把ｉｎｔ改成ｃｈａｒ等等 typedef struct { ElemType *elem;//按要求在宏定义中定义合适的类型 int length;//当前长度 int listsize;//当前分配的存储容量（以sizeof(ElemType)为单位） }SqList; int InitList(SqList *L)//初始化 { L->elem=(ElemType*)malloc(Init_size*sizeof(ElemType)); if(!L->elem) { printf("OVERFLOW") ; return 0; } L->length=0;//当前空表长度为０ L->listsize=Init_size;//初始存储容量 return 1; } int FIND(SqList L,ElemType e) { ElemType *p; int i=1; p=L.elem; for(i=1;i<=L.length;i++) if((*p++)==e) break; if(i<=L.length) return i; else return 0; } int ListInsert(SqList *L ,int i ,ElemType e)//在第ｉ个数之前插入元素, { ElemType *newbase ,*q,*p; int j; if(i<1||i>L->length+1)//ｉ不合法 return 0; if(L->length>=L->listsize)//存储已满 { newbase=(ElemType*)realloc((*L).elem,((*L).listsize+add_size)*sizeof(ElemType)); if(!newbase) { printf("Space is full\n"); return 0;//分配失败 } L->elem=newbase;//新地址 L->listsize=L->listsize+add_size; } for(j=(L->length)-1;j>=i-1;j--)//元素后移 L->elem[j+1]=L->elem[j]; L->elem[j+1]=e;//插入元素 ++L->length;//表长增加 return 1; } int ListDelete(SqList *L,int i)//删除元素 { ElemType e; ElemType *p,*q; int j; if(i<1||i>L->length) return 0; e=L->elem[i-1]; for(j=i;j<L->length;j++)//前移 L->elem[j-1]=L->elem[j]; L->length--; return e; } int main() { int i; SqList L; InitList(&L);//初始化线性表 for(i=1;i<=3;i++) ListInsert(&L,i,i);//向表中按顺序输入３个数 for( i=0;i<3;i++) printf("%d ",L.elem[i]);//输出 printf("\n"); ListDelete(&L,2);//删除第二个数 for( i=0;i<2;i++) printf("%d ",L.elem[i]);//输出 printf("\n"); int ans=FIND(L,3);//寻找数字３所在位置 printf("%d",ans);//因为查找并不改变表中的值所以我们不用传递地址 }

---

合并线性表

Description

已知线性表La、Lb，中的数据元素按值的非递减有序排列，现要求讲La、Lb归为一个新的线性表Lc,使得Lc中的数据元素也是按照值的非递减有序排列。 输入Ｌa的元素个数n1和Lb的元素个数n2 接下来两行输入n1个数和n2个数 表示La和Lb中的元素。

Input

4 7 4 7 8 10 1 3 5 6 8 9 11

Output

1 3 4 5 6 7 8 8 9 10 11

CODE

#include <stdio.h> #include <stdlib.h> #include <string.h> using namespace std; #define Init_size 10//线性表储存空间初始分配量 #define add_size 2//线性表储存空间分配增量 #define ElemType int//定义类型，线性表想存字符就把ｉｎｔ改成ｃｈａｒ等等 typedef struct { ElemType *elem;//按要求在宏定义中定义合适的类型 int length;//当前长度 int listsize;//当前分配的存储容量（以sizeof(ElemType)为单位） }SqList; int InitList(SqList *L)//初始化 { L->elem=(ElemType*)malloc(Init_size*sizeof(ElemType)); if(!L->elem) { printf("OVERFLOW") ; return 0; } L->length=0;//当前空表长度为０ L->listsize=Init_size;//初始存储容量 return 1; } int ListInsert(SqList *L ,int i ,ElemType e)//在ｉ之前插入插入元素, { ElemType *newbase ,*q,*p; int j; if(i<1||i>L->length+1)//ｉ不合法 return 0; if(L->length>=L->listsize)//存储已满 { newbase=(ElemType*)realloc((*L).elem,((*L).listsize+add_size)*sizeof(ElemType)); if(!newbase) { printf("Space is full\n"); return 0;//分配失败 } L->elem=newbase;//新地址 L->listsize=L->listsize+add_size; } for(j=(L->length)-1;j>=i-1;j--)//元素后移 L->elem[j+1]=L->elem[j]; L->elem[j+1]=e;//插入元素 L->length++;//表长增加 return 1; } void MergeList(SqList La,SqList Lb,SqList *Lc) { int i=0,j=0,k=1; int ai,bj; Lc->length=La.length+Lb.length; while(i<=La.length-1&&j<=Lb.length-1) { ai=La.elem[i]; bj=Lb.elem[j]; if(ai<bj) { ListInsert(Lc,k,ai); i++;k++; } else { ListInsert(Lc,k,bj); j++;k++; } } while(i<=La.length-1) { ai=La.elem[i]; ListInsert(Lc,k,ai); i++;k++; } while(j<=Lb.length-1) { bj=Lb.elem[j]; ListInsert(Lc,k,bj); j++;k++; } } int main() { int i; SqList L1,L2,L3; InitList(&L1);//初始化线性表 InitList(&L2); InitList(&L3); int d1=4,d2=7,n; scanf("%d%d",&d1,&d2); for(i=1;i<=d1;i++) { scanf("%d",&n); ListInsert(&L1,i,n);//向表中按顺序输入３个数 } for(i=1;i<=d2;i++) { scanf("%d",&n); ListInsert(&L2,i,n); } MergeList(L1,L2,&L3); for(int i=0;i<d1+d2;i++) printf("%d ",L3.elem[i] ); printf("\n"); }