数据结构与算法：数据结构代码

线性表

一、单链表操作(插入、删除)：

#include<stdio.h>

#include<stdafx.h>

#include<malloc.h>

typedefstructLNode{

intdata;

structLNode*next;

}LNode,*LinkList;

voidInitList(LinkList&L){

〃初始化链表L,带表头结点

L=(LinkList)malloc(sizeof(LNode));

L-〉next=NULL;

}//InitList

voidCreateList(LinkList&L,intn){

〃创建具有n个结点的链表，结点数据由键盘输入

LinkListp;

inti;

for(i=0;i<n;i++){

p=(LinkList)malloc(sizeof(LNode));

scanf&p->data);

p->next=L->next;

L->next=p;

}//for

}//CreateList

voidPrintList(LinkList&L){

〃打印结点的每个元素值

LinkListp;

p=L->next;

printf(〃结点值分别为:\n〃)；

while(p){

printf(〃％d",p->data);

p=p->next;

}//while

printf(〃\n〃);

}//PrintList

voidInsertList(LinkList&L,inti,intn){

〃在的L的第i个位置插入元素n

LinkListp,s;

s=(LinkList)malloc(sizeof(LNode));

intj=0;

P二L;

while(p&&j<i-l){

p=p->next;

j++；

}//while

if(!p||j>i-l){

printf(zzi的值不合法!\n〃)；

return;

}//if

s->data=n;

s->next=p->next;

p->next=s;

}//InsertList

voidDelete(LinkList&L,inti){

〃删除第i个元素

LinkListP,Q;

P=L;

intj=0;

while(P->next->next&&j<i-l){

P=P->next;

j=j+l；

)

if(!P->next)return;

Q=P->next;

P->next=Q->next;

free(Q);

}//Delete

voidmain(){

intn,i,j;

LinkListL;

printf(〃请输入链表结点个数：\n〃)；

scanf(〃%d",&n);

InitList(L);

printf(〃请逆序分别输入结点值:\n〃)；

CreateList(L,n);

PrintList(L);

printf(〃请输入擦人结点位置和值:\n〃);

scanfC%d%d",&i,&j);

InsertList(L,i,j);

PrintList(L);

printf(〃请输入删除结点位置:\n〃)；

scanf("%d",&i);

Delete(L,i);

PrintList(L);

13"E:\考研专业课IDII考

凄输入链表结点个数:"

储逆序分别输入结点值：

5

4

3

2

1

结点值分别为：

12345

请输入擦人结点位置和值：

4100

结点值分别为:

12310045

请输入删除结点仓置:

备点值分别为:

1210045

P>*ft«ssanukeutnnnni:iniift

二、顺序表操作(插入、删除)：

#include"stdafx.h〃

#include<stdio.h>

#include<malloc.h>

#defineInitListSize100

#defineListincrement10

typedefstruct{

int*elem;

intlength;

intLiskSize;

}SqList;

voidInitList(SqList&L){

〃初始化顺序表L

L.elem=(int*)malloc(lnitListSize*sizeof(int));

if(!L.elem){

printf("分配失败!\n");

return;

}//if

L.length=0;

L.LiskSize=InitListSize;

}//InitList

voidInsertList(SqList&L,inti,inte){

〃在顺序表的第i个位置插入元素e

if(i<l||i>L.length){

printfCi的位置不合法!〃)；

return;

}//if

if(L.length+l>InitListSize){

int*newbase;

newbase=(int*)realloc(L.elem,(InitListSize+ListIncrement)*sizeof(int));

if(inewbase){

printf(〃分配失败！\n〃)；

return;

)//if

L.elem=newbase;

L.LiskSize=L.LiskSize+Listlncrement;

}//if

int*p,*q;

q二&(L.elem[i-l]);

for(p=&(L.elem[L.length-1]);p>=q;p--)

*(p+l)=*p;

*q=e;

L.length+=1;

}//InsertList

voidDeleteList(SqList&L,inti,int&e){

〃删除顺序表的第i个位置的值，并用e返回

if(i<l|Ii>L.length){

printfCi的位置不合法!〃)；

return;

}//if

int*p,*q;

q=&(Lelem[i-l]);

e=*q；

p=&(L.elem[L.length-1]);

for(q=q+l;q<=p;q++)

*(qT)=*q;

一L.length;

}//DeleteList

voidPrintList(SqListL){

〃打印顺序表中的所有元素

inti;

for(i=0;i<=L.length-1;i++)

printf(z，%d”,L.elem[i]);

printfCV);

)

voidmain()

inti,n;

intp,q;

SqListL;

InitList(L);

printf(〃请输入元素的个数：\n〃)；

scanf&n);

printf(〃请分别输入各个链表元素:\n〃)；

for(i=0;i<n;i++){

scanf&(L.elem[i]));

}//for

L.length=5;

PrintList(L);

printf(〃请输入擦人元素的位置和值:\n〃);

scanf("%d%d”,&p,&q);

InsertList(L,p,q);

PrintList(L);

printf(〃请输入删除元素的位置:\n〃);

scanf&p);

DeleteList(L,p,q);

PrintList(L);

看t：\考研专业第书・・・

E青输入元素的个数:7

;青分别输入各个链表元素：

1

2

3

4

5

12345

请输入擦人元素的位置和值：

3100

12100345

请输入删除元素的位置;

4

1210045

Pressanykeytocontinue.▼

<II►

三、顺序表操作（合并、交集（另辟空间）、交集（用表A空间））：

#include"stdafx.h〃

#include<stdio.h>

#include<malloc.h>

#defineInitListSize100

#defineListincrement10

typedefstruct{

int*elem;

intlength;

intLiskSize;

}SqList;

voidInitList(SqList&L){

〃初始化顺序表L

L.elem=(int*)malloc(InitListSize*sizeof(int));

if(!L.elem){

printf(〃分配失败！\n〃)；

return;

}//if

L.length=0;

L.LiskSize=InitListSize;

}//InitList

voidCreateList(SqList&L){

//

intn,i;

printf(〃请输入元素的个数:\n〃)；

scanf&n);

printf(〃请分别输入各个链表元素:\n〃)；

for(i=0;i<n;i++){

scanf&(L.elem[i]));

}//for

L.length=n;

)

voidInsertList(SqList&L,inte){

〃在顺序表的结尾插入元素e

if(L.length+l>InitListSize){

int*newbase;

newbase=(int*)realloc(Lelem,(lnitListSize+List!ncrement)*sizeof(int));

if(inewbase){

printf(〃分配失败！\n〃);

return;

}//if

L.elem=newbase;

L.LiskSize=L.LiskSize+Listlncrement;

}//if

L.elem[L.length]=e;

L.length+=1;

}//InsertList

voidPrintList(SqListL){

〃打印顺序表中的所有元素

inti;

for(i=0;i<=L.length-1;i++)

printf(/z%d〃,L.;

printfCW);

)

voidMerge(SqListLa,SqListLb,SqList&Lc){

〃国与Lb都递增，合并后的Lc也递增

int*pa,*pb,*pc,*palast,*pblast;

pa=La.elem;

pb=Lb.elem;

Lc.LiskSize=Lc.length=La・length+Lb.length;

pc=Lc.elem=(int*)malloc(Lc.LiskSize*sizeof(int));

if(!Lc.elem)return;

palast=La.elem+La.length-1;

pblast=Lb.elem+Lb.length-1;

while(pa<=pa1ast&&pb<=pb1ast){

if(*pa〈*pb)*pc++=*pa++;

else*pc++=*pb++;

}//while

while(pa<=palast)*pc++=*pa++;

while(pb<=pblast)*pc++=*pb++;

}//merge

voidInterSet(SqListLa,SqListLb,SqList&Ld){

〃顺序表合并，另辟空间为Ld,可以有相同元素

InitList(Ld);

inti,j=0;

for(i=0;i<La.length;i++){

while(Lb.elem[j]<=La.elem[i]&&j<Lb.length){

if(Lb.elem[j]==La.elem[i])InsertList(Ld,La.elem[i]);

j=j+l；

)

}//for

}//InterSet

voidDeleteList(SqList&L,inti){

〃删除顺序表L.elem[i]

if(i<0||i>=L.length){

printfCi的位置不合法!〃)；

return;

}//if

int*p,*q;

q=&(L.elem[i-l]);

p=&(L.elem[L.length-1]);

for(q=q+l;q<=p;q++)

-L.length;

}//DeleteList

voidInterSet2(SqList&La,SqListLb){

inte,i,j=0;

for(i=0;i<La.length;i++){

if(i>l&&La.elem[i]==La.elem[i-l])La.elem[i]=0;

else{

e=0;

while(j<Lb.length&&Lb.elem[j]<=La.elem[i]){

if(La.elem[i]=Lb.elem[j])e=l;〃出现相同元素标志

)

if(e==0)La.elem[i]=0;〃未出现相同元素

}//if

}//for

i=0;

while(i<La.length){

if(La.elem[i]=0){

DeleteList(La,i);

i=i-l;〃因为删除，后面元素已经迁移

)

i=i+l;

}//while

}//InterSet2

voidmain(intargc,char*argv[])

{

SqListLa,Lb,Lc,Ld;

InitList(La);

InitList(Lb);

CreateList(La);

CreateList(Lb);

Merge(La,Lb,Lc);

printf(〃合并后为:\n〃)；

PrintList(Lc);

InterSet(La,Lb,Ld);

printf("交集为:\n〃)；

PrintList(Ld);

InterSet2(La,Lb);

printf(〃求交集，(用La的空间存放)为:\n〃)；

PrintList(La);

互3任:\考研专业课\书上“.I=II回11^1

恒输入元素的个数：

卷分别输入各个链表元素：

1

2

3

4

5

请输入元素的个数：

请分别输入各个链表元素：

3

4

5

6

7

合并后为：

1233445567

交集为：

条（集:（用人的空间存放）为：

345

Pressanykeytocontinue.

♦IniI►

四、链表逆序合并，允许有相同值：

#include"stdafx.h〃

#include<malloc.h>

#defineN5〃假设每个链表有五个元素

typedefstructLNode{

intdata;

structLNode*next;

}LNode,*LinkList;

voidCreateList(LinkList&L){

〃创建链表L

LinkListP,Q;

inti;

L=(LinkList)malloc(sizeof(LNode));

P=L;

printf(〃请输入链表元素，共5个:\n〃)；

for(i=0;i<N;i++){

Q=(LinkList)malloc(sizeof(LNode));

scanf(〃％d〃,&Q->data);

P->next=Q;

P=P->next;

}//for

P->next=NULL;

}//CreateList

voidMerge(LinkList&La,LinkList&Lb,LinkList&Lc){

LinkListPa,Pb,Pc,Q;

Pa=La->next;

Pb二Lb->next;

Pc=Lc—La

Pc->next=NULL;

while(Pa&&Pb){

if(Pa->data<=Pb->data){

Q=Pa;

Pa=Pa->next;

Q->next=Pc->next;

Pc->next=Q;

)

else{

Q=Pb;

Pb=Pb->next;

Q->next=Pc->next;

Pc->next=Q;

)

}//while

if(Pa){

while(Pa){

Q二Pa;

Pa=Pa->next;

Q->next=Pc->next;

Pc->next=Q;}

)

else{

while(Pb){

Q=Pb;

Pb=Pb->next;

Q->nextzzPc->next;

Pc->next=Q;}

}

free(Lb);

}//Merge

voidPrint(LinkListL){

〃打印链表中所有元素

LinkListP;

P=L->next;

while(P){

printf(〃%d”,P->data);

P=P->next;

)

printf(〃\n〃)；

}//Print

voidmain(intargc,char*argv[])

(

LinkLista,b,c;

CreateList(a);

CreateList(b);

Merge(a,b,c);

printf(/zaandbinversemergeis:\n〃)；

Print(c);

}

;叫：\考研专业课'书..・由』

睛输入链表元素，共5个”

3

4

;青输入链表元素，共5个：

2

3

4

5

6

aandbinversemergeis：

6554433221

Pressanykeytocontinue

4Iiri

五、链表求交集：

#include"stdafx.h〃

#include<malloc.h>

#defineN5〃假设每个链表有五个元素

typedefstructLNode{

intdata;

structLNode*next;

}LNode,*LinkList;

voidCreateList(LinkList&L){

〃创建链表L

LinkListP,Q;

inti;

L=(LinkList)malloc(sizeof(LNode));

P二L;

printf(〃请输入链表元素，共5个:\n〃);

for(i=0;i<N;i++){

Q=(LinkList)malloc(sizeof(LNode));

scanf(〃%d〃,&Q->data);

P->next=Q;

P=P->next;

}//for

P->next=NULL;

}//CreateList

voidInterSet(LinkListLa,LinkListLb,LinkList&Lc){

〃交集为Lc,另辟空间

LinkListPa,Pb,Pc,Q;

Pa=La->next;

Pb=Lb->next;

Lc=(LinkList)malloc(sizeof(LNode));

Pc=Lc;

while(Pa){

while(Pb&&Pb->data<=Pa->data){

if(Pb->data==Pa->data){

Q=(LinkList)malloc(sizeof(LNode));

Q->data=Pb->data;

Pc->next=Q;

Pc=Pc->next;

}//if

Pb=Pb->next;

}//while

Pa=Pa->next;

}//while

Pc->next=NULL;

}//InterSet

voidInterSet2(LinkListLa,LinkListLb,LinkList&Lc){

〃利用a表空间进行交集(不可以出现相同元素)

LinkListQ;

LinkListPa,Pb,Pc;

Pc=Lc=La;

Pa=La->next;

Pb=Lb->next;

while(Pa){

if(!Pc->data||Pa->data!=Pc->data){

while(Pb&&Pb->data<=Pa->data){

if(!Pc->data||Pc->data!=Pb->data){//Pc中不存在与Pb相同的元素

Pc->next=Pa;

Pc=Pc->next;

)

Pb=Pb->next;

}//while

)//if

if(!Pc->data||Pc->data!=Pa->data){〃此结点没有取

Q=Pa;

Pa=Pa->next;

free(Q);

}else(

Pa=Pa->next;

}//if

}//while

Pc->next=NULL;

}//InterSet2

voidPrint(LinkListL){

〃打印链表中所有元素

LinkListP;

P=L->next;

while(P){

printf(z，%d，z,P->data);

P=P->next;

)

printf(〃\n〃);

}//Print

voidmain(intargc,char*argv[])

(

LinkLista,b,c,d;

CreateList(a);

CreateList(b);

InterSet(a,b,c);

printfCaandb另辟空间交集(可以出现相同元素)is:\n〃)；

Print(c);

InterSet2(a,b,d);

printf("aandb利用a表空间进行交集(不可以出现相同元素)is:\n〃)；

Print(d);

B卸考研专业课\书上练习（包括题集）发性表\链表求…互|叵I叵）

箱输入链表元素，共5个：

]

2

3

3

3

请输入链表元素，共5个：

3

3

3

4

4

aandb另辟空间交集（可以出现相同元素）is：

333

aandb利用a表空间进行交集（不可以出现相同元素）is：

3

Pressanykeytocontinue.▼

,IinI，

六、顺序表逆向求交集(真题：0501)：

#include"stdafx.h〃

#include<stdio.h>

#include<malloc.h>

#defineInitsize100

#defineIncrement10

typedefstruct{

int*elem;

intlength;

intListsize;

}SqList;

intN=5;〃假设顺序表中各有五个元素

voidInitList(SqList&L){

L.elem=(int*)malloc(Initsize*sizeof(int));

if(!L.elem)return;

L.length=0;

L.Listsize=Initsize;

}//InitList

voidCreateList(SqList&L){

inti;

charc;

for(i=0;i<N;i++){

scanf(〃％d〃，&L,elem[i]);

c=getchar();

L.length++;

)

}//CreateList

voidInsertList(SqList&L,inte){

if(L.length〉二L.Listsize){

int*newbase;

newbase=(int*)realloc(L.elem,(Initsize+Increment)*sizeof(int));

L.elem=newbase;

}//if

L.elem[L.length]=e;

L.length++;

}//InsertList

voidPrint(SqListL){

inti;

for(i=0;i<L.length;i++)

printf(/z%d”,L.elem[i]);

}//Print

voidInterset(SqListA,SqListB){

SqListC;

InitList(C);

inti,j;

j=B.length-1;

for(i=A.length-1;i>=0;i-){

while(B.elem[j]>=A.elem[i]){

if(B.elem[j]==A.elem[i]){

InsertList(C,B.elem[j]);

)

j=j-l；

}//while

}//for

printf(〃逆向合并后的元素为:\n〃);

Print(C);

}//Interset

voidmain(intargc,char*argv[])

(

SqListA,B;

InitList(A);

InitList(B);

printf("请输入顺序表A元素(5ge):\n〃)；

CreateList(A);

printf("请输入顺序表B元素(5ge):\n，z);

CreateList(B);

Interset(A,B);

printfCV);

■3飞：\考叫业漱・.|a||B|I^Q

清输入顺序表A元素＜5ge〉：

1

2

3

4

5

请输入顺序表B元素＜5ge）：

2

3

4

5

6

逆向合并后的元素为：

5432

Pressanykeytocontinue

七、单链表元素反向逆置(真题：0502)：

#include"stdafx.h〃

#include<stdio.h>

#include<malloc.h>

typedefstructLNode{

intdata;

structLNode*next;

}LNode,*LinkList;

intn;

voidCreateList(LinkList&L){

LinkListP,Q;

inti;

L=(LinkList)malloc(sizeof(LNode));

P=L;

charc;

for(i=0;i<n;i++){

Q二(LinkList)malloc(sizeof(LNode));

scanf&Q->data);

c=getchar();

P->next=Q;

P=P->next;

}//for

P->next=NULL;

)

voidInverseList(LinkList&L){

LinkListP,Q;

P=L->next;

L->next=NULL;

while(P){

Q二P；

P=P->next;

Q->next=L->next;

L->next=Q;

}//while

)

voidPrintList(LinkListL){

LinkListp;

p=L->next;

while(p){

printf(/z%d\n〃,p->data);

p=p->next;

)

voidmain(intargc,char*argv[])

(

LinkListL;

printf(〃请输入链表元素个数:\n〃)；

scanf("%d〃，&n);

printf(〃请输入链表元素:\n〃)；

CreateList(L);

InverseList(L);

printf(〃反向逆置后的链表元素为:\n〃)；

PrintList(L);

)

八、指定结点与后一个结点交换(真题0703)：

#include"stdafx.h〃

#include<stdio.h>

#include<malloc.h>

typedefstructLNode(

intdata;

structLNode*next;

}LNode,*LinkList;

intn;〃链表元素个数

voidExchange(LinkList&L,LinkListP){

〃将P所指的元素与其后一个元素进行交换

LinkListQ;

Q=L;

while(Q->next!=P)Q=Q->next;

Q->next=P->next;

P->next=Q->next->next;

Q->next->next=P;

}//Exchange

voidCreateList(LinkList&L){

〃构造链表

LinkListP,Q;

inti;

L=(LinkList)malloc(sizeof(LNode));

P=L;

for(i=0;i<n;i++){

Q=(LinkList)malloc(sizeof(LNode));

scanf("%d〃，&Q->data);

P->next=Q;

P=P->next;

}//for

P->next=NULL;

}//CreateList

voidPrintList(LinkList&L){

〃打印链表所有元素

LinkListP;

PzzL->next;

while(P){

printf(/z%d〃，P-〉data);

P=P->next;

}//PrintList

voidmain(intargc,char*argv[])

(

LinkListList,P;

printf(〃请输入链表元素个数:\n〃)；

scanf(〃％d〃，&n);

printf(〃请输入链表元素：\n〃);

CreateList(List);

P=List->next->next->next;〃假设p指向第三个结点

Exchange(List,P);

printfCP(假设指向第三个结点)与后一个结点交换后链表元素为:\n〃);

PrintList(List);

printf(〃\rT);

)

1J・E:\考研^业津具雪。7\070?链表交换\Debug\0703链…|[^]

请输入锌表元素个数:Z

请输入链表元素：

1

2

3

4

P（假设指向第三个结点）与后一个结点交换后链表元素为：

12435

Pressanykeytocontinue.▼

«Iin1►

九、静态链表(真题：0806)：

#include"stdafx.h〃

#include<malloc.h>

#defineMAXSIZE11

typedefstruct{

intdata;〃存储数据

intcur;

}component,SLinkList[MAXSIZE];

voidInitSpaceSL(SLinkList&space){

〃将一维数组space中各分量连成一个备用链表，space[0].cur为头指针,

//“0”表示空指针

inti;

for(i=0;i<MAXSIZE-l;++i)space[i].cur=i+l;

space[MAXSIZE-1].cur=0;

}//InitSpaceSL

intMallocSL(SLinkList&space){

〃若备用空间链表非空，则返回分配的结点下标，否则返回0

inti;

i=space[O].cur;

if(space[0].cur)space[0].cur=space[i].cur;

returni;

}//Malloc_SL

voidprint(SLinkListspace,ints){

inti;

printf(〃元素为:\n〃);

for(i=space[s].cur;i<space[0].cur;i++){

printfspace[i].data);

}//for

printfCW);

}//print

voidFree_SL(SLinkList&space,intk){

〃将下标为k的空闲结点回收到备用链表

space[k].cur=space[0].cur;space[0].cur=k;

}//Free_SL

voidDifference(SLinkList&space){

〃依次输入集合A与B的元素，在一维数组space中建立(A-B)U(B-A)

〃的静态链表，s为其头指针。假设备用空间足够大，space[0].cur为其头指针。

ints,r,p,i,j,k;

intm,n,b;

InitSpace_SL(space);

s=MallocSL(space);〃生成头结点

r=s;//r指向s的当前最后结点

printf(〃请输入A与B的元素个数:\n〃);

scanf("%d,%d〃，&m,&n);

printf(〃请分别输入A的元素:\n〃);

for(j=l;j<=m;j++){

i=MallocSL(space);〃分配结点

scanf(z，%d/z,&space[i].data);

space[r].cur=i;〃插入到结尾

r=i;

}//for

space[r].cur=0;〃尾结点的指针为空

printf(〃请分别输入B的元素:\n〃)；

for(j=l;j<=n;j++){

scanf&b);〃依次输入B的元素，如不存在当前表中，则插入，否

则删除

P=s;

k=space[s].cur;〃k指向集合A的第一个结点

while(k!=space[r].cur&&space[k].data!=b){〃在当前表中查找

P=k;

k=space[k].cur;

}//while

if(k-space[r].cur){〃不存在于当前表中

i=Ma11oc_SL(space);

space[i].data二b;

space[i].cur=space[r].cur;

space[r].cur=i;

)//if

else{〃存在，删除

space[p].cur=space[k].cur;

FreeSL(space,k);

if(r==k)r=p;〃若删除是r的所指结点，则需要修改尾指针

}//else

}//for

print(space,s);

"/Difference

voidmain(intargc,char*argv[])

SLinkListspace;

Difference(space);

)

十、从大到小输出键盘输入的数中互不相等的数（真题：0803）：

#include"stdafx.h〃

#include<stdio.h>

#include<malloc.h>

typedefstructLNode{

structLNode*next;

intdata;

}LNode,*LinkList;

voidListinsert(LinkList&L,inte){

〃L递增有序，如果e在L中不存在，则插入，插入后的L依然有序

LinkListp,q;

P二L;

while(p->next&&p->next->data>e)p=p->next;

if(p->next&&p->next->data==e)return;〃存在，无需插入

else{

q二(LinkList)malloc(sizeof(LNode));

q->da