数据结构与算法实验指导书
实验一 线性表的顺序存储实验
一、实验目的
1、掌握用Visual C++6.0上机调试顺序表的基本方法
2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现
二、实验内容
1、顺序表基本操作的实现
[问题描述] 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。
[基本要求] 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。 [实现提示] 要实现基本操作，可用实现的基本操作，也可设计简单的算法实现。 [程序实现]
#include
typedef int DataType ; # define maxnum 20 typedef struct
{int data[maxnum]; int length; }SeqList; /*插入函数*/
int insert(SeqList *L , int i , DataType x) /* 将新结点x插入到顺序表L第i个位置 */ { int j ;
if( i<0 || i>(*L).length +1) { printf(\值不合法 ! \ return 0; }
if((* L).length >=maxnum-1) { printf(\表满不能插入!\ return 0; }
for(j=(*L).length;j>=i;j--) (*L).data[j+1]=(*L).data[j]; (*L).data[i] = x; (*L).length++; return 1; }
/*删除函数*/
int delete( SeqList *L ,int i) /*从顺序L中删除第i个结点*/ { int j ;
if( i<0|| i>(*L).length )
{ printf(\删除位置错误 ! \return 0; }
for(j=i+1;j<=(*L).length;j++) (*L).data[j-1] =(*L).data[j];
- 1 -
数据结构与算法实验指导书
(*L).length--; return 1; }
/*生成顺序表*/
void creatlist(SeqList * L) { int n , i , j ;
printf(\请输入顺序表 L 的数据个数：\\n\scanf(\for(i=0 ; i { printf(\ scanf(\} (*L).length=n-1; printf(\}/*creatlist */ /*输出顺序表 L*/ printout(SeqList * L) { int i ; for (i=0 ; i<=(* L).length ; i++) { printf(\ printf(\}/*printout */ printf(\} main() { SeqList *L ; char cmd ; int i , t , x; clrscr() ; creatlist(L); do { printf(\插入\\n\printf(\删除\\n\printf(\退出\\n\do {cmd=getchar() ; }while((cmd!='i')&&(cmd!='I')&&(cmd!='d')&&(cmd!='D')&&(cmd!='q')&&(cmd!='Q')); switch(cmd) { case 'i': case 'I': printf(\ scanf(\ printf(\ scanf(\ insert(L,i,x) ; - 2 - 数据结构与算法实验指导书 printout(L); break ; case 'd': case 'D' : printf(\ scanf(\ delete(L,i); printout(L); break ; } }while((cmd!='q')&&(cmd!='Q')); } 2、有序顺序表的合并 [问题描述] 已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc [基本要求] lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表 [程序实现] # include { DataType data[maxnum] ; int length ; }SeqList ; int MergeQL(SeqList la , SeqList lb , SeqList *lc) { int i , j , k ; if (la.length+1 + lb.length+1>maxnum) { printf(\return 0; } i=j=k=0; while(i<=la.length && j<=lb.length) { if (la.data[i]<=lb.data[j]) lc->data[k++]=la.data[i++] ; else lc->data[k++]=lb.data[j++]; } /* 处理剩余部分 */ while (i<=la.length) lc->data[k++]=la.data[i++]; while (j<=lb.length) lc->data[k++]=lb.data[j++]; 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 ; - 3 - 数据结构与算法实验指导书 int i ; if (MergeQL(la,lb,&lc)) { printf(\ for(i=0;i<=lc.length ; i++) printf(\} } 实验二 单链表实验 一、实验目的 1、掌握用Visual C++6.0上机调试单链表的基本方法 2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现 二、实现内容 1、单链表基本操作的实现 [问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素 x ，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。 [基本要求]用链式存储结构实现存储 [实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结 点，而要从单链表的头结点开始一个一个地计数寻找。 [程序实现] # include typedef struct node{ DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ }ListNode; void Init_List(ListNode **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; - 4 - 数据结构与算法实验指导书 } 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==j) return p; /*找到了第i个结点*/ else return NULL; /*当i<0或i>0时,找不到第i个结点*/ } void InsertList(ListNode *L,DataType x,int i) { ListNode *p,*s; p=GetNode(L,i-1); /*寻找第i-1个结点*/ if (p==NULL) /*i<1或i>n+1时插入位置i有错*/ { printf(\ return ; } s=(ListNode *)malloc(sizeof(ListNode)); s->data=x;s->next=p->next;p->next=s; } void DeleteList(ListNode *L ,int i) { ListNode *p,*r; p=GetNode(L,i-1); /*找到第i-1个结点*/ if (p==NULL||p->next==NULL) /*i<1或i>n时,删除位置错*/ { printf(\ return ; } r=p->next; /*使r指向被删除的结点a*/ p->next=r->next; /*将ai从链上删除*/ free(r); } /*使用头插法建立带头结点链表算法*/ ListNode * CreatListF(void) { char ch; ListNode *head=(ListNode *)malloc(sizeof(ListNode)); /*生成头结点*/ - 5 -
