数据结构实验1.doc

1、 一、实验目的1、学习线性表的顺序表示和实现，会进行顺序表的插入、删除、合并2、学习线性表的链式表示和实现，会进行链表的插入、删除、合并二、实验内容1、编程实现：（1）在顺序表ajcniydu的第三个位置插入p。（2）删除顺序表ajcniydu第三个位置的元素。2、编程实现将顺序表acdijtuy和cfklns合并。3、编程实现：（1）在链表asdfghjkl的第四个位置插入z。（2）删除顺序表asdfghjkl第四个位置元素。4、编程实现两个有序链表adfi和cefi的合并。三、实验步骤1.+2.代码：#include#includetypedef char ElemType;typedef

2、 struct ElemType *elem; int length; int listsize;SqList;/定义结构体void InitList(SqList &L) L.elem=(ElemType*)malloc(10*sizeof(ElemType); L.length=0; L.listsize=10;/初始化void CreateList(SqList &L,int n) printf(输入字符串：); int i=0; for(i;in;i+)scanf(%c,&L.elemi);L.length+; /赋值void Show(SqList L)int i=0;printf(

3、字符串：);for(i;iL.length;i+)printf(%c,L.elemi); printf(n);/显示int ListInsert(SqList &L, int i, ElemType e) ElemType *p; if (i L.length+1) printf(插入位置不合法！n); else ElemType *q = &(L.elemi-1); for (p = &(L.elemL.length-1); p=q; -p) *(p+1) = *p; *q = e; +L.length; /插入int ListDelete(SqList &L,int i)if(i L.le

4、ngth|i=0)printf(位置不合法n);elseint j = i-1;for( j;jL.length;j+)L.elemj = L.elemj+1;L.length-; / 删除void Mergelist(SqList La,SqList Lb,SqList &Lc)ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa = La.elem;pb = Lb.elem;pa_last = pa + La.length - 1;pb_last = pb + Lb.length - 1;Lc.listsize = Lc.length = La.length

5、+ Lb.length;pc = Lc.elem = (ElemType *)malloc(Lc.length*sizeof(ElemType);while(pa = pa_last & pb = *pb)*pc+ = *pa+;else*pc+ = *pb+;while(pa = pa_last)*pc+ = *pa+;while(pb = pb_last)*pc+ = *pb+;/合并int main()SqList La;InitList(La);CreateList(La,8);ElemType e;int i;printf(输入插入位置及字符：);scanf(%d %c,&i,&e)

6、;ListInsert(La,i,e);Show(La); printf(n);fflush(stdin); SqList Lb;InitList(Lb);CreateList(Lb,8);Show(Lb);printf(输入删除位置：);int j;scanf(%d,&j);ListDelete(Lb,j);Show(Lb); printf(n);fflush(stdin); SqList L1,L2,L3; InitList(L1);InitList(L2);CreateList(L1,8); Show(L1); fflush(stdin); CreateList(L2,6); Show(

7、L2);Mergelist(L1,L2,L3); Show(L3);3. +4.代码：#include#includetypedef char ElemType;typedef struct LNodechar a;ElemType data;struct LNode *next;LNode,*LinkList;/定义结构体int count = 0;void Createlist(LinkList &L,int n)printf(输入字符串：);L = ( LinkList )malloc( sizeof(LNode) );L - next = NULL;int i;LinkList p =

8、 ( LinkList)malloc( sizeof(LNode) );L = p;for( i = 0;i a);q - next = NULL;p - next = q;p = q;count +; /创建链表void Show(LinkList L)LinkList p = ( LinkList )malloc( sizeof(LNode) );p = L - next;printf(字符串为：);while( p )printf(%c,p - a);p = p - next;printf(n);/输出链表int ListInsert( LinkList &L,int n,char K)

9、if( L -next = NULL)printf(链表为空！n);return 0;else if(n count + 1)printf(插入位置不合法！n);return 0;else LinkList p = ( LinkList)malloc( sizeof (LNode);if( n = 1)p - a = K;p - next = L - next;L - next = p;else if( n = count + 1)p = L - next;while( p - next )p = p - next; LinkList q = ( LinkList )malloc( sizeo

10、f (LNode);p - next = q;q - a = K;q - next = NULL;elseint i;p = L;for( i = 1;i next; LinkList q = ( LinkList )malloc( sizeof (LNode);q - a = K;q - next = p - next;p - next = q;count +; / 插入int ListDelete( LinkList &L,int n)if( L - next = NULL)printf(链表为空！n);return 0;else if( n count )printf(删除位置不合法！n

11、);return 0;else LinkList p = ( LinkList )malloc( sizeof (LNode);p = L - next;if( n = 1 )L - next = p - next;free(p);elseint i;for( i = 1;i next;if( n = count )p - next = NULL;elseLinkList q = ( LinkList )malloc( sizeof (LNode);q = p - next;p - next = q - next;free(q);/删除void MergeList(LinkList &La,

12、LinkList &Lb, LinkList &Lc) LinkList pa, pb, pc; pa = La-next; pb = Lb-next; Lc = pc = La; while (pa & pb) if (pa-data data) pc-next = pa; pc = pa; pa = pa-next; else pc-next = pb; pc = pb; pb = pb-next; pc-next = pa ? pa : pb; free(Lb); / 合并int main()LinkList L1;Createlist(L1,9);Show(L1);char b;int

13、 i;printf(输入插入位置和插入元素：);scanf(%d %c,&i,&b);ListInsert(L1,i,b);Show(L1);fflush(stdin);printf(n);LinkList L2;Createlist(L2,9);Show(L2);int j;printf(输入删除元素的位置：);scanf(%d,&j);ListDelete(L2,j);Show(L2);fflush(stdin);printf(n);LinkList La;printf(输入需合并的两组字符串！n);Createlist(La,4);Show(La);fflush(stdin);LinkList Lb;Createlist(Lb,4);Show(Lb);LinkList Lc;MergeList(La,Lb,Lc);Show(Lc);return 0;四、实验小结通过本章学习学会了线性表的顺序表示和实现，会进行顺序表的插入、删除、合并，也学会了线性表的链式表示和实现，会进行链表的插入、删除、合并。但是写码的熟练度有待提高。第 12 页 共 12 页