数据结构 习题1(绪论、线性表)学习资料

数据结构习题

数据结构

第一章习题2for(inti=0;i<=n;i++)

for(intj=0;j<=i;j++)

s;分析：层层递进的关系分步判定

for(inti=1;i<=n;i++)

for(intj=1;j<=i;j++)

for(intk=1;k<=j;k++)

x=x+1;习题3n(n+1)(n+2)/6(n+1)(n+2)/2习题1for(inti=0;i<m;i++)

for(intj=0;j<n;j++)

a[i][j]=i*j;O(m*n)

数据结构

第二章逻辑结构特性：数据元素存在着线性关系

存储结构：顺序存储结构：查找：数组名和元素下标，例a[i]顺序存储结构数组实现

链式存储结构指针实现插入：移动元素， 插入元素，元素个数加1，删除：取出元素， 移动元素，元素个数减1，注意：元素移动的方向

数据结构

第二章习题1：编写一个算法，在额外多使用一个存储单元的前提下,逆置数组元素。

voidrevrese(int

a[],intn){intx,i;for(i=0;i<n/2;i++){x=a[n-i-1];a[n-i-1]=a[i];a[i]=x;}}

数据结构

第二章习题4：编写一个算法，将顺序表中值重复的元素只保留一个，删除其他的，使该表中的所有元素互不相同。

voiddelete(int

a[],intn){

int

i,j,k;for(i=0;i<n-1;i++)

for(j=i+1;j<n;j++)

if(a[i]==a[j]){for(k=j;k<n-1;k++)

a[k]=a[k+1];n--;j--;}}

数据结构

第二章链式存储结构：查找：通过p=p->next，计数器顺链来实现插入：查找第i-1个结点，pre

创建新结点s，改变链，s->next=pre->next;pre->next=s;删除：查找第i-1个结点，pre

取第i个结点r，r=pre->next;

改变链，pre->next=pre->next->next;

释放结点free(r)注意：判空条件：一般链表p->next==NULL;

循环链表p->next==head;

循环控制条件：当前处理位置的结点p是否为表尾等改变链的时候不能将链丢失掉

数据结构

第二章习题2：编写一个算法，返回值为x的结点的序号。

intLocate(LinkList

L,ElemTypex){Node*p;

int

j=1；p=L->next;while(p!=NULL)if(p->data!=x) {p=p->next;j++;}

elsebreak；

if(p==NULL)

return0;elsereturnj;}

数据结构

第二章习题5：编写一个算法，如果在链表中找到了值域为a的结点，则在其后插入一个新结点，否则，将新结点插入到表尾voidinsertnew(LinkList

L,ElemTypea,ElemTypex){Node*p,*s,*pre;s=(Node*)malloc(sizeof(Node));s->data=x;p=L->next;

while(p->next!=NULL)if(p->data!=a) p=p->next;

elsebreak;s->next=p->next;p->next=s;}

数据结构

第二章习题6：设线性表X=(x1,x2,…,xn)，Y=(y1,y2,…,ym)，试编写一个按下列规则合并X,Y为线性表Z的算法，使得：或者线性表X、Y、Z均为单链表作为存储结构。Z=(x1,y1,…,xm,ym,xm+1,…,xn)m<=nZ=(y1,x1,…,yn,xn,yn+1,…,ym)m>n注：单链表的长度值m和n均未显式存储。voidUnit(LinkListX,LinkListY){LinkListZ;

int

m,n;n=Count(X);m=Count(Y);

if(m<=n) Z=Combine(X,Y);else Z=Combine(Y,X);}int

Count(LinkListhead){intcount=0;Node*p;p=head;

while(p!=NULL){ count++; p=p->next;}returncount;}LinkListCombine(LinkListX,LinkListY){

LinkListZ;Node*p,*q,*r;LC=X;p=X->next;q=Y->next;r=Z;while(p!=NULL&&q!=NULL){r->next=p;r=p;p=p->next;r->next=q;r=q;q=q->next;}if(p!=NULL)r->next=p;if(q!=NULL)r->next=q;free(Y);returnZ;}Linklist

CreateFromTail(){LinkListL;Node*r,*s;

intflag=1;

L=(Node*)malloc(sizeof(Node));L->next=NULL;r=L;

while(flag)

{c=getchar();

if(c!=’$’){s=(Node*)malloc(sizeof(Node));

s->data=c;

r->next=s;r=s；}else

{flag=0;r->next=NULL;}}returnL;}习题8:单链表就地逆置voidreverselist(linklistL){p=L->next;L->next=NULL;

while(p!=NULL){q=p->next;

p->next=L->next;L->next=p;p=q

}}Linklist

CreateFromHead(){LinkListL;Node*s;

intflag=1;

L=(Linklist)malloc(sizeof(Node))；

L->next=NULL;

while(flag){c=getchar();

if(c!=’$’){s=(Node*)malloc(sizeof(Node));

s->data=c;

s->next=L->next;L->next=s;}elseflag=0;}returnL;}

LinkListmerge_1(LinkList

LA,LinkListLB)

/*将两个链表的首尾连接起来*/{Node*p,*q;p=LA;q=LB;while(q->next!=LB)q=q->next;

q->next=LA->next;LA->next=LB->next;

free(LB);

return(LA);}习题8:

循环单链表合并

数据结构

第二章例题：假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表的（即A表和B表的）结点空间存放表C。//LA和LB均是带头结点的链表LinkListCombine(LinkList

LA,LinkListLB){ LinkListLC; Node*p,*q; //分别LA的为当前处理结点和后继结点

Node*s,*t; //分别LB的为当前处理结点和后继结点

LC=LA; p=LA->next; s=LB->next; LC->next=NULL;while(p!=NULL&&s!=NULL){if(p->data>=s->data){t=s->next; s->next=LC->next; LC->next=s;