大数据结构实验指导手册簿

1、实用文案实验一线性表的顺序存储实验一、实验目的1、掌握用Visual C+6.0 上机调试顺序表的基本方法2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的 实现二、实验内容1、顺序表基本操作的实现问题描述当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第 i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。基本要求要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。实现提示要实现基本操作，可用实现的基本操作，也可设计简单的算法实现。程序实现#inc

2、lude #include typedef int DataType ;# define maxnum 20typedef structint datamaxnum;int length;SeqList;/*插入函数*/int insert(SeqList *L , int i , DataType x)/*将新结点x插入到顺序表L第i个位置*/ intj ;if( i(*L).length +1) printf( n i值不合法!);return 0;if(* L).length =maxnum-1) printf( n表满不能插入!);return 0;for(j=(*L).length;

3、j=i;j-) (*L).dataj+1=(*L).dataj;(*L).datai = x;(*L).length+;return 1;/*删除函数*/int delete( SeqList *L ,int i)/*从顺序L中删除第i个结点*/ intj ；if( i(*L).length) printf( n 删除位置错误！);return 0;for(j=i+1;jv=(*L).length;j+)(*L).dataj-1 =(*L).dataj;(*L).length-;return 1;/*生成顺序表*/void creatlist(SeqList * L) int n , i ,

4、j ;n);printf(请输入顺序表L的数据个数:scanf(%d , &n);for(i=0 ; in ; i+) printf(data%d = , i);scanf(%d,&(*L).datai);(*L).length=n-1;printf(n);/*creatlist */*输岀顺序表L*/printout(SeqList * L) int i ;for (i=0 ; i=(* L).length ; i+) printf( data%d=, i);printf(%d, (*L).datai);/*printout */printf(n);main() SeqList *L ;ch

5、ar cmd ;int i , t , x;clrscr();creatlist(L);doprintf(ni , I - 插入 n);printf(d , D 删除 n);printf(q , Q 退出 n);docmd=getchar();while(cmd!=i)&(cmd!=T )&(cmd!=d)&(cmd!=D)&(cmd!=q )& (cmd!=Q);switch(cmd) case i:case T:printf(nPlease input the DATA:);scanf(%d, &x);printf(nWhere?);scanf(%d,&i);insert(L,i,x);p

6、rintout(L);break ;case d:case D:printf(nWhere to Delete?);scanf(%d,&i);delete(L,i);printout(L);break ;while(cmd!=q)&(cmd!=Q);2、有序顺序表的合并问题描述已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc基本要求lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表程序实现# include # define maxnum 20typedef int DataType ;typedef struct DataTyp

7、e datamaxnum;int length ;SeqList;int MergeQL(SeqList la , SeqList lb , SeqList*lc) int i , j , k ;if (la .l ength+1 + lb.l ength+1maxnum) printf(narray overflow!);return 0;i=j=k=O;while(i=la .l ength & jdatak+=la.datai+;elselc-datak+=lb.dataj+;/*处理剩余部分*/while (idatak+=la.datai+;while (jdatak+=lb.dat

8、aj+;lc-length=k-1;return 1;main() SeqList la=3,4,7,12,15,4;SeqList lb=2,5,7,15,18,19,5;SeqList lc ;int i ;if (MergeQL(la,lb,&lc) pri ntf(n);for(i=0;i# include vmalloc.h typedef char DataType ;typedef struct nodeDataType data;/*结点的数据域*/struct node *next; /* 结点的指针域 */ListNode;void lnit_List(ListNode *

9、L)(*L)=(ListNode *)malloc(sizeof(ListNode);/*产生头结点 */(*L)-next=NULL;int List_Length(ListNode *L )int n=0;ListNode *p=L-next; while(p!=NULL)n+;p=p-next;return n;ListNode* GetNode(ListNode *L,int i)int j;ListNode *p;p=L;j=0;/*从头结点开始扫描*/while(p-next&j!=i)/*顺指针向后扫描，直到p-next 为NULL或i=j为止*/p=p-next;j+;if(i

10、=j)return p;/*找到了第i个结点*/elsereturn NULL; /*当i0时，找不到第i个结点*/void InsertList(ListNode *L,DataType x,int i)ListNode *p,*s;p=GetNode(L,i-1); /* 寻找第 i-1 个结点 */if (p=NULL)/*in+1时插入位置i有错*/ printf(position error);return ;s=(ListNode *)malloc(sizeof(ListNode);s-data=x;s-next=p-next;p-next=s;void DeleteList(Li

11、stNode *L ,int i)ListNode *p,*r;p=GetNode(L,i-1);/* 找到第 i-1 个结点 */if (p=NULL|p-next=NULL)/*in 时，删除位置错 */ printf(position error);return ;r=p-next;/*使r指向被删除的结点a*/p-next=r-next;/* 将 ai 从链上删除 */free(r);/*使用头插法建立带头结点链表算法*/ListNode * CreatListF(void)char ch;ListNode *head=(ListNode *)malloc(sizeof(ListNod

12、e);/* 生成头结点 */ListNode *s;/* 工作指针 */head-next=NULL;ch=getchar(); /*读入第1个字符*/while(ch!=n)s=(ListNode *)malloc(sizeof(ListNode);/* 生成新结点 */s-data=ch;/*将读入的数据放入新结点的数据域中*/s-next=head-next;head-next=s;ch=getchar();/* 读入下一字符 */return head;/*使用尾插法建立带头结点链表算法*/ListNode * CreatListRI(void)char ch;ListNode *he

13、ad=(ListNode *)malloc(sizeof(ListNode);/* 生成头结点 */ListNode *s,*r;/* 工作指针 */r=head;/*尾指针初值也指向头结点 */while(ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);s-data=ch;r-next=s;r=s;r-next=NULL;/*终端结点的指针域置空，或空表的头结点指针域置空*/return head;/*复制链表 A中的内容到表 B中*/void copy(ListNode *a, ListNode *b)ListNode *pa=a

14、-next; ListNode *u;ListNode *rb=b;while(pa!=NULL)u=( ListNode *)malloc(sizeof(ListNode);u-data=pa-data;rb-next=u;rb=u;pa=pa-next;rb-next=NULL;/*输岀带头结点的单链表*/void DisplaySL(ListNode *la, char *comment) ListNode *p ;p=la-next ;if(p) printf(n%sn , comment);while(p) printf(%4c,p-data);p=p_next;printf(n);

15、/*主函数*/main() ListNode *la ,*lb,*lc, *p ;int n,x,i;printf(n用头插法建立链表la，请输入节点内容：)；la=CreatListF();DisplaySL(la,新生成链la节点内容:);printf(n 链表 la 的长度:%2d,List_Length(la);printf(n请输入要插入的元素:);scanf(%c, &x);printf(n请输入要插入的位置：);scanf(%d,&i);InsertList(la,x,i);DisplaySL(la,插入后链la节点内容);printf(n请输入要删除元素的位置：);scanf(

16、%d,&i);DeleteList(la,i);DisplaySL(la,删除后链la节点内容);printf(n用尾插法建立链表lb，请输入节点内容:);fflush(stdin);lb=CreatListR1();DisplaySL(lb,新生成链lb节点内容:);Init_List (&l c);copy(la,lc);DisplaySL(lc,复制生成的链lc节点内容:);2、有序单链表的合并la和 lb中的数据问题描述已知单链表la和lb中的数据元素按非递减有序排列，将 元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。基本要求不破坏la表和lb表的结构。程序实现#

17、 include #include#define NULL 0typedef int DataType;typedef struct SLNode DataType data;struct SLNode * next;slnodetype;int MergeSL(slnodetype *la,slnodetype *lb,slnodetype *lc);int CreateSL(slnodetype*la,int n);void DisplaySL(slnodetype *la , char * comment);main() slnodetype *la, *lb, *lc ,*p;int

18、n,m;la=(slnodetype *)malloc(sizeof(slnodetype);la-next=NULL;lb=(slnodetype *)malloc(sizeof(slnodetype);lb-next=NULL;lc=(slnodetype *)malloc(sizeof(slnodetype);lc-next=NULL;printf(n 输入链la节点数:);scanf(%d,&n);printf(n 输入链la节点内容:);CreateSL(la,n);DisplaySL(la,链 la 节点内容:);printf(n 输入链lb节点数:);scanf(%d,&m);p

19、rintf(n 输入链lb节点内容:);CreateSL(lb,m);DisplaySL(lb,链 lb 节点内容:);if(MergeSL(la,lb，&lc)DisplaySL(lc,合成后的链 lc:);getchar();int MergeSL(slnodetype * la ,slnodetype *lb,slnodetype * *lc) slno detype * pa, * pb, * pc;lc=(slnodetype *)malloc(sizeof(slnodetype);pa=la-next;pb=lb-next;pc= *lc;while(pa&pb)pc-next=(

20、slnodetype*)malloc(sizeof(slnodetype); pc=pc-next;if(pa-datadata) pc-data=pa-data;pa=pa-next;else pc-data=pb-data;pb=pb-next;while (pa) /* 插入la链的剩余段 */ pc-next=(slnodetype*)malloc(sizeof(slnodetype); pc=pc-next;pc-data=pa-data;pa=pa-next;/*插入lb链的剩余段*/while(pb)pc-next=(slnodetype*)malloc(sizeof(slnod

21、etype); pc=pc-next;pc-data=pb-data;pb=pb-next;/*生成单链表*/int CreateSL(slnodetype *la ,int n) int i ;slno detype*p , *q ;q=la ;for (i=1 ; idata); q_next=p;q=p;q-next=NULL ;return 1 ;/*输岀单链表*/void DisplaySL(slnodetype *la, char *comment) slnodetype *p ;p=la-next ;if(p) printf(n%sn , comment);while(p) pr

22、intf(n%3d , p-data);p=p-next ;printf(n);实验三循环链表实验一、实验目的1、掌握用Visual C+6.0 上机调试循环链表的基本方法2、进一步掌握循环单链表的插入、删除、查找算法的实现二、实现内容1. 约瑟夫环问题问题描述设有N个人围坐一圈，现从某个人开始报数， 数到M的人出列，接着从出 列的下一个人开始重新报数，数到M的人以岀列，如此下去，直到所有人都岀列为此。试设计确定他们的岀列次序序列的程序。基本要求选择单向循环链表作为存储结构模拟整个过程，并依次输岀列的各人的编号。实现提示程序运行之后，首先要求用户指定初始报数的下限值，可以n=30,此题循环链表

23、可不设头节点，而且必须注意空表和非空表的界限。女口 n=8, m=4 时，若从第一个人，设每个人的编号依次为 1，2，3，开始报数,则得到的出列次序为4， 8，5，2，1，3，7，6，如下图所示，内层数字表示人的编号，每个编号外层的数字代表人岀列的序号。程序实现#include #include typedef struct node int num;struct node *next;linklist;linklist *creat(head,n) /*使n个人围成一圈，并给每个人标识号数*/linklist *head;int n ;linklist *s,*p;int i;s=(link

24、list * )malloc(sizeof(linklist);head=s;s-num=1;p=s;for(i=2;inum=i;p-next=s;p=s;p-next=head;return(head);/* creat */linklist * select(linklist *head, int m) linklist *p, *q;int i, t;p=head; t=1;q=p; /* q为p的前趋指针*/p=p_next;dot=t+1 ;/* 报一次数 */if(t%m=0) printf(%4d, p-num);q-next=p-next;free(p);p=q_next;e

25、lse q=p;p=p-next;while(q!=p);head=p;printf(%4d,p-num);return (head);/* select */main() int n,m;linklist *head;printf(ninput the total number:n=);scanf(%d, & n);printf(ninput the number to call:m=);scanf(%d, & m);head=creat(head,n);head=select(head,m);printf(nthe last one is :%d, head-num);/* main */

26、思考题：编程实现两个循环单链表的合并。实验四 栈、队列的实现及应用一、实验目的1、 掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用2、掌握栈和队列的特点，即先进后岀与先进先岀的原则。3、掌握栈和队列的基本操作实现方法。二、实验内容1、实现栈的顺序存储# define MAXSIZE 100typedef int ElemType;typedef struct ElemType dataMAXSIZE;int top;SeqStack;void lnitStack(SeqStack *s)s-top=0;return 1;int StackEmpty(SeqStack *s)

27、 if(s-top=0) return 1;else return 0;int StackFull(SeqStack *s) if(s-top=MAXSIZE-1)return 1;else return 0;void Push(SeqStack *s,int x) if (StackFull(s) printf(the stack is overflow!); return 0;else s-datas-top=x;s-top+;void Display(SeqStack *s)if(s-top=0)printf(the stack is empty!n);else while(s-top!

28、=0) printf(%d-,s-datas-top); s-top=s-top-1;ElemType Pop(SeqStack *s) if(StackEmpty(s) return 0;else return s-data-s-top;ElemType StackTop(SeqStack *s) int i;if(StackEmpty(s) return 0;else i=s-top-1;return s-datai;/*返回栈顶元素的值，但不改变栈顶指针*/main(SeqStack *p)int n,i,k,h,x1,x2,select;printf(create a empty st

29、ack!n);InitStack(p);printf(input a stack lengthen);scanf(%d,&n);for(i=0;i%dn,x1);display(p);break;case 4:x2=StackTop(p); printf(x2-%d,x2); break;2、利用栈实现数制转换# define MAXSIZE 100typedef int ElemType ；/*将顺序栈的元素定义为整型 */typedef struct ElemType dataMAXSIZE;int top;SeqStack;void lnitStack(SeqStack *s)s-top

30、=0;return 1;int StackEmpty(SeqStack *s) if(s-top=0) return 1;else return 0;int StackFull(SeqStack *s) if(s-top=m-1) else return 0;return 1;void Push(SeqStack *s,int x) if (StackFull(s)printf(the stack is overflowin);return 0;标准文档else s-datas-top=x;s-top+;ElemType Pop(SeqStack *s) ElemType y;if(Stack

31、Empty(s) printf(the stack is empty!n); return 0;else y=s-datas-top;s-top=s-top-1;return y;ElemType StackTop(SeqStack *s) if(StackEmpty(s) return 0;else return s-datas-top;void Dec_to_Ocx (int N)SeqStack *S ;ElemType x ;Init_SeqStack(S)；/* n是非负的十进制整数，输岀等值的八进制数/*定义一个顺序栈*/*初始化栈*/*/if(Nfront=0;p_rear=0;

32、return 1;int enqueue(seqqueue *q, int e) if(q-rear+1)%maxsize=q-front) return 0;elseq_dataq_rear=e; q-rear=(q-rear+1)%maxsize; return 1;int dequeue(seqqueue *q)int e;if (q-front=q-rear) return 0; e=q-dataq-front; q-front=(q-front+1)%maxsize; return e;int empty(seqqueue *q)int v;if (q_front=q_rear)v=

33、1;else v=0;return v; int gethead(seqqueue *q)int e;if (q-front=q-rear) e=-1;else e=q-dataq-front; return e;void display(seqqueue *q)int s;s=q-front;printf(the sequeue is display:n);if (q-front=q-rear)printf(the sequeue is empty!);else while(srear)printf(-%d, q-datas); s=(s+1)%maxsize;printf(n);main(

34、seqqueue *head) int n,i,m,x,y,select,xq;printf(create a empty sequeuen);sqinit(head);printf(please input the sequeue length:n); scanf(%d,&n);for (i=O;irear:%dn,head-rear); printf(head-front:%dn,head-front); display(head);printf(select 1 * enqueue() n);printf(select 2 * dequeue() n);printf(select 3 *

35、 empty() n);printf(select 4 * gethead() n);printf(select 5 * display() n);printf(please select (1-5):);scanf(%d, &select);switch(select)case 1: printf(please input a value :n );scanf(%d, &x);enqueue(head,x);display(head);break;case 2: dequeue(head);display(head);break;case 3: if(empty(head)printf(th

36、e sequeue is empty); elseprintf(the sequeue is full);case 4: y=gethead(head);printf(output head value:%dn,y);break;case 5: display(head);break;实验五串及数组的实验一、实验目的1、 了解串及数组的两种存储方法，掌握数组在作为存储结构中的地址计算方法。2、了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会稀疏矩阵运算采 用的处理方法。二、实验内容1、顺序串的基本操作#define MaxSize 100typedef structchar strMaxS

37、ize;int len; strtype;void assign(strtype *s,char t)int i=0;while (ti!=0)s-stri=ti;i+;s-stri=0;s-len=i;void strcopy(strtype *s,strtype t)int i;for (i=O;istri=t.stri;int length(strtype s)return(s.len);int equal(strtype s,strtype t)int i=0;if (s.l en!=t.len) return(0);elsefor (i=0;is .l en;i+)if (s.str

38、i!=t.stri) return(0); return(1);strtype concat(strtype s,strtype t)strtype r;int i,j;for (i=0;is .l en;i+)r.stri=s.stri;for (j=0;jv=t.len;j+)r.strs.len+j=t.strj;r.len=i+j;return(r);int index(strtype s,strtype t)int i,j,k;for (i=0;s.stri;i+)for (j=i,k=0;s.strj=t.strk;j+,k+)if (!t.strk+1)return(i);ret

39、urn(-1);strtype substr(strtype s,int i,int k)strtype t;int j;for (j=i;js-len)printf(位置参数值错误n);elsefor (j=i;jlen;j+)r.strj-i=s-strj;r.len=j-i;r.strr.len=O：for (j=0;jstri+j=t.strj;for (j=0;jstri+t.len+j=r.strj;s-len=s-len+t.len;s-strs-len=0;void delete(strtype *s,int i,int k)int j;if (is-len | i+ks-le

40、n) printf(位置参数值错误n); else/*将s的第i个位置之后的字串复制到/*将t串连接到s的第i个字符之后*/*将r串连接到s串之后*/*修改s串长度*/r中*/for (j=i+k;jlen;j+)/*将s的第i+k个位置之后的字串前移s-strj-k=s-strj;s-len=s-len-k;/* 修改 s 的长度 */s-strs-len=0;strtype replace(strtype s,strtype t,strtype v)k位*/int i;i=index(s,t);while (i=0)delete(&s,i,t.len);insert (&s,i,v);i=

41、index(s,t);return(s);void display(strtype s)printf(字符串：sn,s.str);main()strtype s,t,r,v;assign (&s,aababababad);assign(&t,aba);assign(&v,121);display(s);display(t);display(v);printf(s 长度=%dn,length(s); printf(t 与 v 连接); display(concat(t,v);printf(s中的t替换成v后的);display(replace(s,t,v);2、三元组稀疏矩阵的基本操作#incl

42、ude #define Max 100#define M 3#define N 3#define K 3typedef int smatMax3;void display();void creatmat(int AMN,smat B)/*A是一个稀疏矩阵,B是产生的相对应的三元组存储*/int i,j,k=1;for (i=O;iM;i+)/*按行优先顺序扫描 A的元素，不为0者存入B中*/for (j=O;jN;j+)if (A【ij!=0)B【k【0=i;B【k【1=j;B【k【2=A【ij;k+;B00=M;B01=N;B02=k-1;/*存入非0元素个数*/int findval(smat A,int x)int i,t;t=A02;/*非0元素个数*/i=1;while (i=t & Ai2!=x) i+;/* 查找等于 x的元素值 */if (i0)q=1;for (col=0;c