数据结构习题集（李冬梅 第2版）C语言版源程序汇总 算法2.1---8.6

1、数据结构习题集(李冬梅第2版)C语言版源程序汇总 include include using namespace std;/函数结果状态代码Idefine OK 1铲define ERROR 04define OVERFLOW -2 /Status是函数的返回值类型，其值是函数结果状态代码 typedef int Status;结点的数据域/结点的指针域/LinkList为指向结构体LNode的指结点的数据域/结点的指针域/LinkList为指向结构体LNode的指typedef struct LNode (int data;struct LNode *next;LNode, *LinkLis

2、t;针类型Status InitList (LinkList &L);/初始化Status DestroyList (LinkList SL);销毁链表void CreateList_R (LinkList &L, int L_Data , int n);/后插法创立单链表void MergeList (LinkList &LA, LinkList &LB, LinkList &LC); 合并void PrintList (LinkList L);输出徒表int main() (int laData=3,5,8,11);int lbData = 2,6,8,9,11,15,20;LinkLis

3、t la, lb;InitList(la);InitList(lb);CreateList_R(la,laData,sizeof(laData)/sizeof(laData0);CreateList_R(lbzlbData,sizeof(IbData)/sizeof(IbData0);LinkList 1c;InitList(1c);MergeList(la,lb,1c); coutcc合并后的线性表为：”;PrintList(lc);DestroyList(lc);return 0;/初始化生成新结点作为头结点，用头指针L指向头结点 /头结点的指针域置空Status InitList(Lin

4、kList &L) /构造一个空的单链表LL=new LNode;L-next=NULL; return OK; 销毁链表Status DestroyList(LinkList &L)while(L)while(pa)(n+；pa=pa-next;输出结果：差运算后的线性表为：None 3 - 5 该集合的元素个数为：2 才include 4include using namespace std;/函数结果状态代码define OK 1Idefine ERROR 0define OVERFLOW -2 /Status是函数的返回值类型，其值是函数结果状态代码 typedef int Statu

5、s;/结点的数据域结点的指针域/LinkList为指向结构体LNode的指针类/结点的数据域结点的指针域/LinkList为指向结构体LNode的指针类typedef struct LNode (int data;struct LNode *next;LNode, *LinkList;型Status InitList (LinkList &L);初始化Status DestroyList (LinkList &L);/箱毁链表void CreateList_R (LinkList &L, int L_Data , int n) ; /后插法创立单链表void Decompose (LinkLi

6、st &A, LinkList SB, LinkList &C);分解锥表void PrintList (LinkList L);输出链表int main() (int A_Data=2z-6,8,9,-llz15,-20;LinkList A;InitList(A);CreateList_R(A,A_Data,sizeof(A_Data)/sizeof(A_Data(0);LinkList B,C； Decompose(ArB,C);cout”分解后的有序表分别为：next;) return false;遍历下一个结点遍历下一个结点void Output()输出数据couti : ;Link

7、List p=HTi-next; while(p)输出散列地址/p初始化为链表的首元结点coutp-data; p=p-next;if(p) cout) coutendl;)void initHash()(for(int i=O;inext=NULL;int main()(initHash();int n;cinn;for(int i=0;in;i+) Insert_K();Output ();Delete_K();Output ();return 0;输入输出0:71:1 82:23:34:45:56:60:71:82:23:34:45:5forfint i=0;iLENGTH;i+)6:6

8、include #include using namespace std;函数结果状态代码#define OK 1#define ERROR 0 /define OVERFLOW -2 /Status是函数的返回值类型，其他是函数结果状态代码 typedef int Status;结点的数据域结点的指针域/LinkList为指向结构体LNode的指结点的数据域结点的指针域/LinkList为指向结构体LNode的指初始化销毁链表/后插法创立单链表简单项选择择排序输出链表typedef struct LNode ( int data; struct LNode *next;LNode, *Lin

9、kList; 针类型Status InitList(LinkList &L);Status DestroyList(LinkList iL);void CreateList_R(LinkList SLf int L_Data, int n); void SelectSort(LinkList &L);void PrintList(LinkList L);int main() ( int n; cout”请输入锥表长度： cinn;int *lData=new intn;cout “请输入关键字以空格隔开：”； for(int i0;in;i+) (cinlData (i; )LinkList

10、1;InitList(1);CreateList_R(lzIData,n);SelectSort(1);coutnext-NULL;头结点的指针域置空return OK; 销毁鞋表 Status DestroyList(LinkList &L) ( while(L) ( LNode *p=L; L=L-next; delete p;/释放空间 return OK;后插法创立单链表void CreateList_R(LinkList &L,int L_Data,int n) (/正位序输入n个元素的值，建立带表头结点而单链表LLNode *r = L;for (int i0;idata=L_Da

11、tai; p-next=NULL; r-nextp; r=p;输出链表void PrintList(LinkList L) (LNode *p=L;p-p-next;while(p)coutp-data p=p-next;)coutendl;简单项选择择排序void SelectSort(LinkList &L) 基于单链表的简单项选择择排序LNode *p=L-next;while(p!=NULL)(LNode *qp-next;LNode *r=p;while(q!NULL) if(q-datadata) r=q;/尾指针r指向头结点/生成新结点/初始化p的数据域为L_Data i 将新结

12、点*P插入尾结5”之后 /r指向新的尾结点*p/p指向首元结点顺链域向后扫描，直到p为空/r是指向关键字最小的结点的指针q=q-next；)if (r!=p)交换r和p的数据域int temp=r-data;r-data=p-data;p-datatemp;)p=p-next;p指向下一个结点)输出结果请输入链表长度：6请输入关犍字以空格隔开：8 5 7 1 0 1 排序结果：0 115 7 8 4include #include using namespace std;/函数结果状态代码define OK 1#define ERROR 0#define OVERFLOW -2 /Status

13、是函数的返回值类型，其值是函数结果状态代码双向链表双向链表初始化/销毁链表L_Data , int n);/后插法创立双向链表/双向冒泡排序输出链表typedef int Status;typedef struct DuLNode ( int data;struct DuLNode *prior,*next; DuLNode, *DuLinkList;Status InitList(DuLinkList &L);Status DestroyList(DuLinkList &L); void CreateList_R(DuLinkList &L,int void DuplexSort(DuLin

14、kList &L); void PrintList(DuLinkList L);int main() ( int n; cout请输入锥表长度：; cinn;int *lData-new intn; cout“请输入关键字以空格隔开：； for(int i0;in;i+) cinlData i;)DuLinkList 1;InitList(1);CreateList_R(l/IData,n);DuplexSort (1);coutprior=L;L-next=L; return OK; 情毁链表Status DestroyList(DuLinkList &L) (while(L) DuLNod

15、e *p=L;L=L-next;delete p;糅放空间) return OK; 后插法创立双向链表void CreateList_R(DuLinkList &L,int L_Data(,int n) (正位序输入n个叁素的值，建立带表头结点的会向链表LDuLinkList p=new DuLNode;p-data=L_Data0;L-next=p;p-prior=L;p-next*NULL;for(int i=l;idataL_Datai;p-prior=L;L-next-prior=p; p-next=L-next; L-next=p;/输出链表void PrintList(DuLink

16、List L)依次输出链表中的数据DuLinkList p=L-next; while(p!=NULL) (coutdatanext;)coutendl;双向冒泡排序是否发生交换的标记双向链表头，向下冒泡的开始结点 /双向链表尾，向上冒泡的开始结点p是工作指针，指向当前结点假定本趟无交换向卜冒泡，每一趟使一最大元素沉底交换两结点指针，涉及6条锌/有交换先将结点从倦表上摘卜./将temp插到结点*p前无交换，指针后移准备向上起泡交换两结点指针，涉及6条健有交换先将temp结点从链表上摘下/将temp插到p结点后(右)无交换，指针前移准备向下起泡/while(exchange)void Duple

17、xSort(DuLinkList &L)(对存储在带头结点的双向链表L中的元素进行双向冒泡排序int exchange=l;DuLinkList head,tail,p,temp;head=L;tail=NULL;while(exchange)if(head-next=tail)break;p=head-next;exchange=O;while(p-next!=tail)if(p-data p-next-data)(temp=p-next;exchanger；p-next=temp-next;if(temp-next!=NULL)temp-next-prior=p;temp-next=p;p

18、-prior-next=temp;temp-prior=p-prior; p-prior=temp;else p=p-next;)tail=p;p=tail-prior;while(exchange & p-prior!=head)if(p-data prior-data)(temp=p-prior;exchanged;p-prior=temp-prior; temp-prior-next=p; temp-prior=p;p-next-prior=temp;temp-next=p-next; p-next=temp;else p=p-prior;)head=p;输出结果请输入链表长度：5请输入

19、关健字以空格隔开：8 6 16-4排序结果：-4 16 6 8 ilinclude using namespace std;void Process(int az int n)对数组a中的n个关键字进行整理/使所有关键字为负值的记录排在关键字为非负值的记录之前 int low=Orhigh=n-l;while(lowhigh)while(lowhigh&alow0) low+；while(low=0) high-;if(lowhigh)(int temp=alow;alowahigh;ahigh=temp;low+;high-;找到从左到右的非负值记业找到从右到左的负值记录如果需要交换，即lo

20、whigh/交换记录继续向后找void PrintA(int a,int n) 输出数据for(int i=0;in-l;i+) coutaicoutan-1endl;int main ()int n;cout请输入数组长度:;cinn;int *a=new intn;cout”请输入关键字以空格隔开：;for(int i=0;in;i+)cina i;Process (a, n);/数组的正负排序cout排序结果：；PrintA(a,n);输出数据return 0;输出结果请输入数组长度：5请输入关键字以空格隔开：-1 9 7 2 -4排序结果：-1 -4 7 2 9/基于快排思想的查找#i

21、nclude using namespace std;int Search (int r,int low,int high,int key)1/在数组r low. .high中台找关键字值等于key的记录 while(lowkey&rhighkey)1OW+； high-; ) while(lowkey) high-; /从右侧开始找到第一个不大于关键字的记录，其位置为high if (r high=key)查找成功返回其位置return high; while(low=high & rlowkey)low+； /从左侧开始找到第一个不小于关键字的记录，其位置为low if (r low=ke

22、y)查找成功返回其位置return low; ) coutHNot findendl;/查找失败return -1; int main() ( int n; coutn; int rn; coutc(”请输入数组元素：； for(int i=0;in;i+) cinr i;int key; coutkey;int p=Search (r, 0, n-1, key); 查找 if(p!-l) cout该元素在数组中的位置为：p+l,endl;return 0; 输出结果 请输入数组长度：6 请输入数组元素：9 5 1 3 8 2 请输入要查找的元素：9 该元素在数组中的位置为：1#include

23、using namespace std;void CountSort(int a z int bz int n)计数排序，将包括n个数据的数组a中的记录排序存入到数组b中 intfor(i=0;in;i+)/针对数组中的每个关键字(for(j=0zc=0;jn;j+)/统计关键字比当前关键字小的元素个数if(a(jai) C+;b(c=ai;根据比当前关键字小的元素个数将当前关键字存放在数组b中)int main()int n;coutn;int iza100,b100;cout “请输入关键字以空格隔开：”;for (i=0;in;i+) cina i;Countsort (a,bzn);/

24、计数排序cout”排序结果：”； for(i=0;in-l;i+) coutbicoutbn-l endl;输出结果请输入数组长度：6请输入关健字以空格隔开：8 4 9 1 7 5排序结果：1 4 5 7 8 9#include using namespace std;int Partition(int az int n)将正整数构成的集合划分为两个不相交的子集A1和A2int low=0,high-n-1;int low0=0,highO=n-l;int sl=0,s2=0;int flagl;int k=n/2;分别指向表的下界和上界 分别指向新的子表的卜界和上界 /分别记录A1和R2中元

25、素的和 /标记划分是否成功记录表的中间位宣while(flag) (int pivotkey=alow;while(lowhigh) while (low=pivotkey) -high;if(low!=high)a lov; =a high;while(lowhigh & alow=pivotkey)+1OW；while(flag) (int pivotkey=alow;while(lowhigh) while (low=pivotkey) -high;if(low!=high)a lov; =a high;while(lowhigh & alow=pivotkey)+1OW；循环进行划分选

26、择枢轴从两端交替地向中间扫描从最右侧位置依次向左搜索/将比枢轴记录小的记录移到低端从最左侧位置依次向右搜索if(low!=high)ahigh=alow； )alow=pivotkey;if(low=*k-l)flag=0;else/将比枢轴记录大的记录移到高端枢轴记录到位满足条件，枢轴的位置是n/2的前一位置.划分成功，卜次循环将退出划分继续划分/满足条件，枢轴low及之前的所有元素均属于A11ow0=+1qw;high=highO;1ow0=+1qw;high=highO;维续对low之后的元素进行划分else/满足条件，枢轴low及之后的所有元素均属于A2highO=high;继续对lo

27、w之前的元素进行划分lov/=lowO; ) COUt”Al中的元素：”； for(int i=0;ik;i+) (coutaisl+=ai;求解子集Al中元素的和 coutendl;coutA2中的元素：; for(int i=k;in;i+) coutais2+=ai;求解子集A2中元素的和)coutendl;cout IS1-S2 | 的值为：Hs2-slerKil; return s2-sl;int main() (int n;coutn;int an;cout”请输入数组元素：， for(int i=0;inext=NULL;return OK;情毁链表Status DestroyL

28、ist(LinkList &L) ( while(L) LNode *p=L; L=L-next; delete p;释放空间) return OK; 后插法创立单链表void CreateList_R(LinkList &LZ int L_Data),int n)(正位序输入n个关素的值，建立带表头结点M单链表LLNode *r - L;/尾指针r指向头结点for (int i=0;idata=L_Data i;/初始化 p 的数据域为 L_Data ip-next=NULL; r-next=p; 将新结点*p插入尾结点*r之后 r=p;指向新的尾结点) 输出链表void PrintList

29、(LinkList L) ( LNode *p=L;coutNone;p=p-next;while(p) (cout,r - p-data;p=p-next;coutendl;/分解链表void Decompose(LinkList &A,LinkList &B/LinkList &C) /单链表A分解为两个具有相同结构的链表B和CB=A;LNode *p=A-next;B-next=NULL;C=new LNode;C-next=NULL;B=A;LNode *p=A-next;B-next=NULL;C=new LNode;C-next=NULL;p为工作指针B表初始化为C申请结点空间C初

30、始化为空表while(p!=NULL)while(p!=NULL)表A未到达表尾结点LNode *r=p-next;暂存p的后继if (p-datanextB-next; B-next=p; ) else将大于0的结点链入C表,前插法( p-next=C-next; C-next=p; ) p=r;/p指向新的待处理结点|输出结果：分解后的有序表分别为：None - -20 -11 -6 None - 15 - 9 - 8 2 #include dinclude using namespace std;函数结果状态代码#define OK 1#define ERROR 04define OVE

31、RFLOW -2 /Status是函数的返回值类型，其值是函数结果状态代码 typedef int Status;结点的数据域结点的指针域/LinkList为指向结构体LNode的指针类结点的数据域结点的指针域/LinkList为指向结构体LNode的指针类初始化梢毁链表后插法创立单链表求最大值输出链表typedef struct LNode (int data;struct LNode *next;LNode, *LinkList; 型Status InitList(LinkList &L);Status DestroyList(LinkList &L);void CreateList_R(

32、LinkList iL,int L_Data, int n); int Max(LinkList L);void PrintList(LinkList L);int main() (int laData=2,-6,8,9,-11,15,-201;LinkList la;InitList(la);CreateList_R(la,laData,sizeof(laData)/sizeof(laData0);int lamax=Max(la);cout琏表 la 中的最大值为：lamaxnext=NULL;头结点的指针域置空return OK; /销毁链表 Status DestroyList(Lin

33、kList &L) ( while(L) LNode *p=L; L=L-next； delete p;释放空间 return OK;后插法创立单链表void CreateList_R(LinkList &L,int L_Data I ,int n)/正位序输入n个元素的值，建立带表头结点初单链表LLNode *r = L;尾指针r指向头结点for (int i=0;idata=L_Data i;初始化 p 的数据域为 L_Dataip-next=NULL; r-next=p; /将新结点*p插入尾结点*r之后 r=p;r指向新的尾结点*p) 输出链表void PrintList(LinkLi

34、st L) (LNode *p=L;coutNone;p=p-next;while(p) (coutn - p-data;p=p-next;)coutendl; 求最大值int Max(LinkList L) 确定单链表中值最大的结点 if(L-nextNULL) return NULL; LNode *pmax=L-next;pmax 指向首元结点LNode *p=L-next-next;指向第二个结点while (p!=NULL)遍历链表，如果下一个结点存在if(p-datapmax-data)pmax=p;pmax指向数值大的结点p-p-next;p指向下一个结点，继续遍历) retur

35、n pmax-data; 输出结果:链表la中的最大值为：15 #include #include using namespace std;/函数结果状态代码 #define OK 1 define ERROR 0 金define OVERFLOW -2 /Status是函数的返回值类型，其位是函数结果状态代码 typedef int Status;/结点的数据域结点的指针域/LinkList为指向结构体LNode的指针类typedef struct LNode ( int data;struct LNode *next;LNode, *LinkList;型Status InitList (L

36、inkList &L);/初始化Status DestroyList (LinkList &L);销毁链表void CreateList_R (LinkList 5L, int L_Data , int n);/后插法创立单链表void Inverse (LinkList &L);逆转链表void PrintList (LinkList L);输出链表int main() (int laData=2,-6,8,9f-llz15,-20;LinkList la;InitList(la);CreateList_R(la,laData,sizeof(laData)/sizeof(laData0);I

37、nverse(la);coutnext=NULL;头结点的指针域置空return OK;销毁链表 Status DestroyList(LinkList &L) (while(L)(LNode *p=L;L=L-next;delete p;释放空间) return OK; /后插法创立单链表 void CreateList_R(LinkList iLz int L_Data,int n) (正位序输入n个元素的值，建立带表头结点初单链表LLNode *r - L;/尾指针r指向头结点for (int i=0;idata=L_Data i;/初始化 p 的数据域为 L_Data ip-next=

38、NULL; r-next=p; /将新结点*p插入尾结点*r之后 r-p;/r指向新的尾结点/输出鞋表void PrintList(LinkList L) (LNode *p=L;coutNone;p=p-next;while(p) (coutn - Mp-data; p=p-next;)coutendl;逆转链表void Inverse(LinkList &L) 逆置带头结点的单链表L LNode *p=L-next;L-next=NULL;while(p!=NULL)LNode *q=p-next; p-next=L-next; L-next=p;pq；p指向首元结点头结点的指针域置为空遍

39、历链表，如果卜一个结点存在/q指向*p的后继 /p插入在头结点之后输出结果：链表 la 逆置后为：None - -20 15 -11 9 - 8 -6 - 2#include #include using namespace std;函数结果状态代码4define OK 1Idefine ERROR 0#define OVERFLOW -2/Status是函数的返回值类型，其值是函数结果状态代码 typedef int Status;typedef struct LNode(int data;结点的数据域struct LN ode *next;结点的指针域LNodez *LinkList;/L

40、inkList 为指向结构体 LNode 的指针类型Status InitList (LinkList &L);初始化Status DestroyList (LinkList &L);/梢毁链表void CreateList R (LinkList &L, int L_Data , int n); /后插法创立单链表void DeleteMinMax (LinkList SL, int mink, int maxk);删除最大值和最小值之间的元素void PrintList (LinkList L);输出链表int main()(int laData=2,6,8,9f 11,15,20;Lin

41、kList la;InitList(la);CreateList_R(lazlaData,sizeof(laData)/sizeof(laData0);int min-7,max-11;DeleteMinMaxla,min,max);cout链表la删除介于至Umaxnext=NULL;头结点的指针域置空return OK; 销毁链表 Status DestroyList(LinkList &L) ( while(L)LNode *p=L;LL-next;delete p;) return OK;释放空间/后插法创立单链表void CreateList_R(LinkList &LZ int L

42、_Data,int n)/正位序输入n个亮素的值，建立带表头结点M单链表LLN ode *r = L;尾指针r指向头结点for (int i0; Kn; + + i) LNode *p=new LNode; p-data=L_Datai; p-next=NULL; r-next=p; r=p;生成新结点/初始化p的数据域为L_Data i 将新结点*P插入尾结*r之后 /r指向新的尾结点*p输出链表void PrintList(LinkList L) (LNode *p=L;cout,None;p=p-next;while(p) (cout一 p-data; p=p-next;)coutend

43、l;/删除最大值和最小值之间的元素void DeleteMinMax(LinkList &L,int mink,int maxk)(删除递增有序链表L中值大于mink且小于maxk的所有元素p指向首元结点/pre指向头结点行找第一个值大于mink的结点/pre指向前驱结点/位找第一个值大于等于maxk的结点修改待删除结点的指针依次释放待删除结点的空间LNode *p=L-next;LNode *pre = L;while(p&p-datanext;)while(p&p-datanext;LNode *q=pre-next;pre-next=p;while(q!=p)(LNode *s=q-ne

44、xt;delete q;q=s;输出结果:链表la删除介于7到11之间的元素后变为：None 2 6 11 15 20 #include #include using namespace std;函数结果状态代码#define OK 1#define ERROR 0#define OVERFLOW -2 /Status是函数的返回值类型，其值是函数结果状态代码 typedef int Status;结点的数据域指向直接前驳指向直接后继/DuLinkList 为指向结构体 DuLNode结点的数据域指向直接前驳指向直接后继/DuLinkList 为指向结构体 DuLNode初始化销毁链表n);后

45、插法创立循环双链表交换前后结点输出链表typedef struct DuLNode (int data;struct DuLNode *next;struct DuLNode *prior;DuLNode, *DuLinkList; 的指针类型Status InitList(DuLinkList iL);Status DestroyList(DuLinkList &L);void CreateListR(DuLinkList &L,int L_Data, void Exchange(DuLinkList p);void PrintList(DuLinkList L);int main() (i

46、nt l_Data=lz2z3;DuLinkList 1;InitList (1);CreateList_R(l,l_Data,sizeof(l_Data)Zsizeof(l_Data0);cout ”双向链表为：，PrintList(1);DuLNode *p = l-next-next;cout p 指向的是： p-data endl;Exchange(p);cout ”交换后的双向链表为：”；PrintList (1);DestroyList (1);return 0; /初始化Status InitList(DuLinkList &L) 构造个空的单链表LL=new DuLNode;生

47、成新结点作为头结点，用头指针L指向头结点L-prior=L;头结点的前驱指针指向自身L-next=L;头结点的后继指针指向自身return OK; 销毁链表Status DestroyList(DuLinkList &L) (DuLNode *p = L;while(p !- L) (DuLNode *q=p;p=p-next;delete q;释放空间) return OK; /后插法创立循环双链表void CreateList_R(DuLinkList &LZ int L_Data(,int n) (正位序输入n个元素的值，建立带表头结点的高环双链表LDuLNode *r - L;尾指针r

48、指向头结点for (int i=0;idata=L_Datai;初始化p的数据域为L_Dataip-next=L; r-next=p;p-prior=r;L-prior=p;将新结点*p插入尾结点”之后r=p;)/r指向新的尾结点*p输出链表void PrintList(DuLinkList L) (DuLNode *p=L;coutNone;pp-next;while(p!=L) (coutn p-data; p=p-next;)coutendl;I交换void Exchange(DuLinkList p)对应图2.20 对应图2.20 /对应图2.20 /对应图2.20 /对应图2.20

49、对应图2.20 对应图2.20/在双向循环锥表，交换p所指向的结点及其前驱结点的顺序DuLNode *q=p-prior; q-prior-next=p; p-prior=q-prior; q-next=p-next; q-prior=p; p-next-priorq; p-next=q;输出结果：双向锥表为：None 1 2 3林放空间林放空间LNode *p=L; L=L-next; delete p;)return OK;|后插法创立单链表void CreateList_R(LinkList &LZ int L_DataI), int n)正位序输入n个元素的值，建立带表头结点而单链表L

50、LNode *r = L;尾指针r指向头结点for (int i=0;idata=L_Datai; p-next=NULL; r-next=p; r=p;LNode *p=new LNode; p-data=L_Datai; p-next=NULL; r-next=p; r=p;生成新结点初始化p的数据域为L_Data i 将新结点*p插入尾结1”之后/r指向新的尾结点*p输出链表void PrintList(LinkList L) (LNode *p=L;coutNone;p=p-next; while(p)cout p-data; p=p-next;coutendl;合并void Merg

51、eList(LinkList &La,LinkList &LbzLinkList &Lc) 将两个递增的有序链表La和Lb合并为一个递增的有序链表LcLNode *pa=La-next;pa是链表La的工作指针，初始化为首元结点LNode *pb=Lb-next;/pb是链表Lb的工作指针，初始化为百元结点/pa和pb分别是链表La和Lb的工作指针，初始化为相应链表的首元结点 Lc=La; LNode *pc=La;/用La的头结点作为Lc的头结点while (pa&pb)两个锥表La和Lb均未到达表尾结点( if(pa-datadata) 取较小者La中的元素，将pa链接在pc的后面，pa指

52、针后移 pc-next=pa;pc-pa; pa=pa-next;)else if (pa-datapb-data)取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移 pc-next=pb;pc=pb;pbpb-next;)else相等时取La中的元素，删除Lb中的元素 pc-next=pa;pc=pa;p指向的是：2交换后的双向链表为：None 2 1 3 #include linclude using namespace std;函数结果状态代码#define OK 1#define ERROR 0#define OVERFLOW -2 /Status是函数的返回值类型，其值是函数

53、结果状态代码 typedef int Status;#define MAXSIZE 100typedef struct SqList (int *elem;int length;SqList;Status InitList(SqList &L);Status DestroyList(SqList &L);Status GetElem(SqList L,int i,int &e);Status Listinsert(SqList 8L,int i,int e); void Deleteltem(SqList &A,int item);void PrintList(SqList L);int ma

54、in () (SqList 1;InitList (1);Listinsert (1,lf1);Listinsert(1,2,3);Listinsert (1,3,3);Listinsert (1,4,4);cout啜性表为： PrintList(1);int item = 3;Deleteltem(1,item);cout(删除”后的线性表为： PrintList (1);DestroyList(1);return 0; 初始化Status InitList(SqList &L) /构造一个空的顺序表LL.elem=new intMAXSIZE;if(!L.elem) exit(OVERFL

55、OW);存储数据的基地址当前个数顺序存储结构为SqList初始化销毁顺序表/取值插入删除顺序表A中所有值为item的元素/输出顺序表存储数据的基地址当前个数顺序存储结构为SqList初始化销毁顺序表/取值插入删除顺序表A中所有值为item的元素/输出顺序表为顺序表分配一个大小为MAXSIZE的数组空间存储分配失败退出空表长度为0L.length = 0; return OK;销毁顺序表Status DestroyList(SqList &L)if(L.length)( delete L.elem; L.length = 0;)取值Status GetElem(SqList L,int i,in

56、t &e) (if(iL.length) return ERROR; e=L.elemi-l;return OK;释放空间表长又变成0/判断i位是否合理，假设不合理，返回ERROR单元存储第i个数据元素/插入Status Listinsert(SqList &L, int i,int e)在顺序表L中第i个位置插入新的元素e, i值的合法范围是liL.length+lif (iL.length+1) return ERROR; if(L.length=MAXSIZE) return ERROR; for(int j=L.length-1;j=i-l;j-)L.elemj+l=L.elemj;L

57、.elemi-le;+L.length;return OK;/i值不合法当前存储空间已满插入位置及之后的元索后移 将新元素e放入第i个位置表长加1输出顺序表void PrintList(SqList L) (cout n;for(int i=l;i=L.length;i+)(int e;GetElem(L,i,e);coute;if (i !=L. length) cout, )cout) endl;/删除顺序表A中所有值为item的元素 void Deleteltem(SqList &AZ int item) (删除顺序表A中所有值为item的元素int k0;for(int i=0;iA.

58、length;i+) if(A.elem(i!=item) A.elemk=A.elemi; k+;)A. length=k;/k记录值不等于item的元素个数从前向后扫描顺序表杳找值不为item的元素利用原表的空间记录值不为item的元素不等于item的元素增1顺序表A的长度等于k输出结果：线性表为：1, 3, 3, 4 删除3后的线性表为：1, 4 仙include #include using namespace std;函数结果状态代码用define OK 14define ERROR 0#define OVERFLOW -2 /Status是函数的返回值类型，其值是函数结果状态代码t

59、ypedefint Status;typedefstruct LNodeintdata;struct LNode *next;LNode, *LinkList; 型结点的数据域/结点的指针域/LinkList为指向结构体LNode的指针类初始化销毁链表后插法创立单链表查找倒数第k个结点输出链表生成新结点作为头结点，用头指针L指向头结点头结点的指针域置空Status InitList(LinkList &L);Status DestroyList(LinkList iL);void CreateListR(LinkList &L,int L_Data,int int Search_k(LinkL

60、ist list,int k);void PrintList(LinkList L);int main()int laData(=2z-6,8,9,-11,15,-20,6, 8);LinkList la;InitList(la);CreateList R(la,laData,sizeof(laData)/sizeof(laData0);cout”链表 la 为：”;PrintList(la);int k=7;int a=Search_k(la,7);if(a=l)cout查找成功endl;elsecoutU喳找失败nextNULL;return OK;销毁徒表Status DestroyLi