数据结构C语言--基础实验

实验1 线性表的顺序实现

1.！顺序表的倒置

/**********************************/
/*文件名称：lab1-01.c             */
/**********************************/
/*基于sequlist.h中定义的顺序表，编写算法函数reverse(sequence_list *L)，实现顺序表的就地倒置。*/
#include "sequlist.h"
/*请将本函数补充完整，并进行测试*/
void reverse(sequence_list *L)
{int i,j;datatype x;i=0;j=L->size-1;while (i<j){x=L->a[i];L->a[i]=L->a[j];L->a[j]=x;i++;j--;}
}int main()
{sequence_list L;		/*定义顺序表*/input(&L);	        		/*输入测试用例*/print(&L);                  /*输出原表*/reverse(&L);print(&L);                  /*输出新表*/
}

2.分类，奇数存放到存到顺序表L2中，偶数存到顺序表L3中

/**********************************/
/*文件名称：lab1_02.c             */
/**********************************//*编写一个算法函数void sprit( sequence_list *L1,sequence_list *L2,sequence_list *L3)，
将顺序表L1中的数据进行分类，奇数存放到存到顺序表L2中，偶数存到顺序表L3中，编写main()进行测试。
*/#include "sequlist.h"
/*请将本函数补充完整，并进行测试*/
void sprit(sequence_list *L1,sequence_list *L2,sequence_list *L3)
{int i,j,k;i=j=k=0;for (i=0;i<L1->size;i++){if (L1->a[i]%2==1)L2->a[j++]=L1->a[i];elseL3->a[k++]=L1->a[i];}L2->size=j;L3->size=k;
}
int main()
{   sequence_list L1,L2,L3;		/*定义三个顺序表*/input(&L1);				    /*输入L1*/sprit(&L1,&L2,&L3);		    /*对L1进行分类*/print(&L1);				    /*输出L1、L2和L3*/print(&L2);print(&L3);
}

3.！将L1与L2中的数据合并到L3中，使数据在L3中按升序排列

/*已知顺序表L1，L2中数据由小到大有序，请用尽可能快的方法将L1与L2中的数据合并到L3中，使数据在L3中按升序排列。*/#include "sequlist.h"
/*请将本函数补充完整，并进行测试*/
void merge(sequence_list *L1,sequence_list *L2,sequence_list *L3)
{int i,j,k;i=j=k=0;while (i<L1->size && j<L2->size ){if (L1->a[i]<L2->a[j])L3->a[k++]=L1->a[i++];elseL3->a[k++]=L2->a[j++];}while (i<L1->size)L3->a[k++]=L1->a[i++];while (j<L2->size)L3->a[k++]=L2->a[j++];L3->size=k;}
int main()
{sequence_list L1,L2,L3;input(&L1);				/*输入时请输入有序数据*/input(&L2);				/*输入时请输入有序数据*/merge(&L1,&L2,&L3);		/*合并数据到L3*/print(&L3);				/*输出L3*/
}

4.！实现求顺序表la与lb的交集存放到顺序表lc中

/*假设顺序表la与lb分别存放两个整数集合，函数inter(seqlist *la,seqlist *lb,seqlist *lc)
的功能是实现求顺序表la与lb的交集存放到顺序表lc中,请将函数补充完整.  */
/**********************************/
/*文件名称：lab1_04.c                 */
/**********************************/
#include "sequlist.h"
/*请将本函数补充完整，并进行测试*/
void  inter(sequence_list *la,sequence_list *lb,sequence_list *lc)
{int i,j,k;k=0;for (i=0; i<la->size; i++){j=0;while (j<lb->size  &&  la->a[i]!=lb->a[j])j++;if (j<lb->size)lc->a[k++]=la->a[i];}lc->size=k;
}
int main()
{sequence_list la,lb,lc;inputfromfile(&la,"1.txt"); 		/*从文件1.txt建立顺序表*/inputfromfile(&lb,"2.txt");		/*从文件2.txt建立顺序表*/print(&la); 				 	    /*输出la*/print(&lb);  				        /*输出lb*/inter(&la,&lb,&lc);   		/*求la与lb的交集存于lc中*/print(&lc); 					    /*输出lc*/return 0;
}

5.！！将顺序表L中的所有奇数调整到表的左边，所有偶数调整到表的右边

/*
请编写一个算法函数partion(sequence_list *L)，尽可能快地将顺序表L中的所有奇数调整到表的左边，
所有偶数调整到表的右边，并分析算法的时间复杂度。
*/
/**********************************/
/*文件名称：lab1_05.c                 */
/**********************************/
#include "sequlist.h"
/*请将本函数补充完整，并进行测试*/
void partion(sequence_list *L)
{int i, j;           // 定义两个指针i和jdatatype x;         // 定义临时变量xi = 0;              // 初始化i为表头位置j = L->size - 1;    // 初始化j为表尾位置do {while (i < j && L->a[i] % 2 == 1)   // 从表头向表尾查找第一个偶数元素i++;while (i < j && (L->a[j] & 0x1) == 0)   // 从表尾向表头查找第一个奇数元素j--;if (i < j) {    // 如果i<j，表示找到了需要交换的元素x = L->a[i];         // 交换元素位置L->a[i++] = L->a[j];L->a[j--] = x;}} while (i < j);    // 当i<j时继续循环}int main()
{sequence_list L;inputfromfile(&L,"3.txt");print(&L);  						/*输出表L*/partion(&L);print(&L);  						/*输出新表*/return 0;
}

实验2不带头结点的单链表

1.删除不带头结点单链表head中第一个值为x 的结点。

/*编写函数slnklist delx(linklist head, datatype x)，删除不带头结点单链表head中第一个值为x 的结点。
并构造测试用例进行测试。
*/
/**********************************/
/*文件名称：lab2_01.c                            */
/**********************************/
#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
linklist delx(linklist head,datatype x)
{linklist  pre,p;pre=NULL;p=head;while (p &&p->info!=x){pre=p;p=p->next;}if (p){if (pre==NULL)head=p->next;elsepre->next=p->next;free(p);}return head;}int main()
{   datatype x;linklist head;head=creatbyqueue();		/*尾插入法建立单链表*/print(head);printf("请输入要删除的值：");scanf("%d",&x);head=delx(head,x);			/*删除单链表的第一个值为x的结点*/print(head);delList(head);				/*释放单链表空间*/return 0;
}

2.！！！将不带头结点的单链表head就地 倒置

/**********************************/
/*文件名称：lab2_02.c                 */
/**********************************/
/*
假设线性表（a1,a2,a3,…an）采用不带头结点的单链表存储，
请设计算法函数linklist reverse1(linklist  head)和
void reverse2(linklist *head)将不带头结点的单链表head就地 倒置，
使表变成（an,an-1,…a3.a2,a1）。并构造测试用例进行测试。
*/
#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
linklist reverse1(linklist head)
{linklist p, s;  // 定义两个指针p和sp = head;       // 将p指向头节点head = NULL;    // 初始化反转后的链表头节点为空while (p)       // 当p非空时进行循环{s = p;                  // 保存p节点p = p->next;            // 移动p指针到下一个节点s->next = head;         // 将s节点的next指针指向反转后的链表头节点head = s;               // 更新反转后的链表头节点为s节点}return head;    // 返回反转后的链表头节点
}void reverse2(linklist *head)
{linklist p,s;p=*head;*head=NULL;while (p){s=p;p=p->next;s->next=*head;*head=s;}
}int main()
{   datatype x;linklist head;head=creatbystack();		    /*头插入法建立单链表*/print(head);				            /*输出原链表*/head= reverse1(head);		/*倒置单链表*/print(head);				            /*输出倒置后的链表*/reverse2(&head);			        /*倒置单链表*/print(head);delList(head);return 0;
}

3.！！插入

/*
假设不带头结点的单链表head是升序排列的，设计算法函数linklist insert(linklist head,datatype x)，
将值为x的结点插入到链表head中，并保持链表有序性。
分别构造插入到表头、表中和表尾三种情况的测试用例进行测试。
*/
/**********************************/
/*文件名称：lab2_03.c                 */
/**********************************/
#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
linklist insert(linklist head ,datatype x)
{linklist pre,p,s;pre=NULL;p=head;while ( p && p->info<x ){pre=p;p=p->next;}s=(linklist )malloc(sizeof(node));s->info=x;if (pre==NULL){s->next=head;head=s;}else{s->next=p;pre->next=s;}return head;
}
int main()
{   datatype x;linklist head;printf("输入一组升序排列的整数：\n");head=creatbyqueue();				/*尾插入法建立单链表*/print(head);printf("请输入要插入的值：");scanf("%d",&x);head=insert(head,x);				/*将输入的值插入到单链表适当位置*/print(head);delList(head);return 0;
}

4.删除

/*
编写算法函数linklist delallx(linklist head, int x)，删除不带头结点单链表head中所有值为x的结点。
*/
/**********************************/
/*文件名称：lab2_04.c                 */
/**********************************/
#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
linklist delallx(linklist head,int x)
{linklist  pre,p;pre=NULL;p=head;while(p){while (p &&p->info!=x)            //找值为x的结点{pre=p;p=p->next;}if (p)                                          //找到了{if (pre==NULL)                 //删除的结点为第一个结点{head=p->next;free(p);p=head;}else                                    //删除的结点不是第一个结点{pre->next=p->next;free(p);p=pre->next;}}}return head;
}
int main()
{   datatype x;linklist head;head=creatbyqueue();				/*尾插入法建立单链表*/print(head);printf("请输入要删除的值：");scanf("%d",&x);head=delallx(head,x);print(head);delList(head);return 0;
}

实验3 带头结点的单链表

1.删除带头结点单链表head中第一个值为x 的结点

/*编写函数void delx(linklist head, datatype x)，删除带头结点单链表head中第一个值为x 的结点。
并构造测试用例进行测试。
*/
/**********************************/
/*文件名称：lab3_01.c                 */
/**********************************/
#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
void delx(linklist head,datatype x)
{linklist pre,p;pre=head;p=head->next;while (p && p->info!=x)         //查找{pre=p;p=p->next;}if (p)                                          //删除{pre->next=p->next;free(p);}}int main()
{   datatype x;linklist head;head=creatbyqueue();		/*尾插入法建立带头结点的单链表*/print(head);printf("请输入要删除的值：");scanf("%d",&x);delx(head,x);			/*删除单链表的第一个值为x的结点*/print(head);delList(head);				/*释放单链表空间*/return 0;
}

2.带头结点的单链表head就地倒置

/**********************************/
/*文件名称：lab3_02.c                 */
/**********************************/
/*
假设线性表（a1,a2,a3,…an）采用带头结点的单链表存储，请设计算法函数void reverse(linklist  head)，
将带头结点的单链表head就地倒置，使表变成（an,an-1,…a3.a2,a1）。并构造测试用例进行测试。
*/
#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
void reverse(linklist head)
{linklist p,s;p=head->next;head->next=NULL;while (p){s=p;p=p->next;s->next=head->next;head->next=s;}
}
int main()
{   datatype x;linklist head;head=creatbystack();			/*头插入法建立带头结点的单链表*/print(head);					/*输出原链表*/reverse(head);			/*倒置单链表*/print(head);					/*输出倒置后的链表*/delList(head);return 0;
}

！！！：是否带头结点的差别（带：第一个实际结点：head->next; 不带：第一个实际结点：head）

linklist p,s;
p=head;head=NULL;
while(p)
{s=p;p=p->next;s->next=head;head=s;
}

// 带头结点的单链表
linklist p,s;
p=head->next;
head->next=NULL;
while (p)
{s=p;p=p->next;s->next=head->next;head->next = s;
}

3.插入

/*
假设带头结点的单链表head是升序排列的，设计算法函数linklist insert(linklist head,datatype x)，
将值为x的结点插入到链表head中，并保持链表有序性。
分别构造插入到表头、表中和表尾三种情况的测试用例进行测试。
*/
/**********************************/
/*文件名称：lab3_03.c                 */
/**********************************/
#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
void  insert(linklist head ,datatype x)
{linklist pre,p,s;pre=head;p=head->next;while (p && p->info<x)      {pre=p;p=p->next;}s=(linklist)malloc(sizeof(node));s->info=x;s->next=p;pre->next=s;
}
int main()
{   datatype x;linklist head;printf("输入一组升序排列的整数：\n");head=creatbyqueue();				/*尾插入法建立带头结点的单链表*/print(head);printf("请输入要插入的值：");scanf("%d",&x);insert(head,x);				    /*将输入的值插入到带头结点的单链表适当位置*/print(head);delList(head);return 0;
}

4.删除

/*
编写算法函数void  delallx(linklist head, int x)，删除带头结点单链表head中所有值为x的结点。
*/
/**********************************/
/*文件名称：lab3_04.c                 */
/**********************************/
#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
void  delallx(linklist head,int x)
{linklist pre,p;pre=head;p=head->next;while(p){while (p &&p->info!=x)      //查找{pre=p;p=p->next;}if (p)                                      //找到了{pre->next=p->next;free(p);p=pre->next;                    //删除后p回到pre的后继结点}}
}
int main()
{   datatype x;linklist head;head=creatbyqueue();				/*尾插入法建立带头结点的单链表*/print(head);printf("请输入要删除的值：");scanf("%d",&x);delallx(head,x);print(head);delList(head);return 0;
}

5.！！！将head中的结点按结点值 升序排列

/*
已知线性表存储在带头结点的单链表head中，请设计算法函数void sort(linklist head)，将head中的结点按结点值升序排列。
*/
/**********************************/
/*文件名称：lab3_05.c                 */
/**********************************/
#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
void sort(linklist head)
{linklist pre, q, p, s;p = head->next;     // 将p指向链表的第一个节点head->next = NULL;  // 将头节点的next指针置为空，相当于创建一个空的链表while (p) {s = p;          // 保存p节点p = p->next;    // 移动p指针到下一个节点pre = head;     // 初始化pre指针为头节点q = head->next; // 初始化q指针为头节点的下一个节点while (q && q->info < s->info) {    // 找到s节点的插入位置，即找到第一个比s大的节点位置pre = q;q = q->next;}s->next = q;    // 将s节点插入到pre和q之间pre->next = s;  // 修改pre的next指针，将s节点插入到pre和q之间}
}int main()
{        linklist head;head=creatbyqueue();   		/*尾插法建立带头结点的单链表*/print(head);    			    /*输出单链表head*/sort(head);     				/*排序*/print(head);delList(head);return 0;
}

6.

实验5  递归

1.！！！！求数组a[left..right]中的最大数

/*编写递归算法int max(int a[],int left, int right)，求数组a[left..right]中的最大数。
*/#include "ArrayIo.h"
/*请将本函数补充完整，并进行测试*/
int max(int a[],int left,int right)
{int lmax,rmax,mid;if (left==right) return a[left];else{mid=(left+right)/2;lmax=max(a,left,mid);rmax=max(a,mid+1,right);return lmax>rmax?lmax:rmax;}}
int main()
{   int a[10];input(a,10);print(a,10);printf("数组的最大数是:%d\n",max(a,0,9));return 0;
}

2.！！！！将数组a[left..right]中的所有奇数调整到表的左边，所有偶数调整到表的右边。

/*
请编写一个递归算法函数void partion(int a[], int left, int right)，
将数组a[left..right]中的所有奇数调整到表的左边，所有偶数调整到表的右边。
*/
#include "ArrayIo.h"
#define N 10
/*请将本函数补充完整，并进行测试*/
void partion(int a[], int left, int right)
{int x;if (left < right){while (left < right && a[left] % 2 == 1)  // 从左边找到第一个偶数left++;while (left < right && a[right] % 2 == 0)  // 从右边找到第一个奇数right--;if (left < right){x = a[left];a[left] = a[right];a[right] = x;  // 交换左边的偶数和右边的奇数partion(a, left + 1, right - 1);  // 递归处理剩余部分}}
}int main()
{   int a[N];init(a,N);				/*随机产生N个数*/print(a,N);partion(a,0,N-1);print(a,N);return 0;
}

3.！！！！！！！冒泡法进行升序排序   采用二分查找法在数组a[left..right]中查找值为key的元素所在的位置

这是一个经典的冒泡排序算法，使用递归的方式实现。具体步骤如下：

1. 首先判断数组长度 n 是否大于0。
2. 设置一个标志 flag 为0，用于标记本轮循环是否发生交换操作。
3. 遍历数组，比较相邻的元素，如果前面的元素大于后面的元素，则交换它们，并将 flag 设置为1。
4. 如果本轮循环发生了交换操作，则递归调用 bubbleSort 函数对长度为 n-1 的子数组进行排序。
5. 递归结束条件是数组长度 n 不大于0。

这是一个经典的二分查找算法，使用递归的方式实现。具体步骤如下：

1. 首先判断左指针 left 是否大于右指针 right，如果大于则表示找不到目标元素，返回-1。
2. 否则，计算中间位置 mid，并判断中间元素与目标元素的大小关系：
   • 如果中间元素等于目标元素，则返回中间位置 mid。
   • 如果目标元素小于中间元素，则在左半部分继续查找，即调用 binSearch 函数查找左半部分。
   • 如果目标元素大于中间元素，则在右半部分继续查找，即调用 binSearch 函数查找右半部分。

通过以上步骤，可以在有序数组中高效地查找目标元素的位置。

 

/*请编写递归函数void bubbleSort(int a[],int n)，对长度为n的数组采用冒泡法进行升序排序。请编写递归函数int binSearch(int a[], int left, int right,int key)，采用二分查找法在数组a[left..right]中查找值为key的元素所在的位置，若查找失败函数返回-1。*/#include "ArrayIo.h"
#define N 10
/*请将本函数补充完整，并进行测试*/
void bubbleSort(int a[],int n)
{    int i,t;int flag;if(n>0){flag=0;for(i=0;i<n-1;i++){if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;flag=1;}}if (flag==1) bubbleSort(a,n-1);}return ;
}
int binSearch(int a[], int left,int right,int key)
{int mid;if (left>right)return -1;else{mid=(left+right)/2;if (a[mid]==key)return mid;elseif (key<a[mid])return binSearch(a,left,mid-1,key);elsereturn binSearch(a,mid+1,right,key);}
}
int main()
{   int x,pos,a[N];init(a,N);bubbleSort(a,N);print(a,N);printf("请输入要查找的数：\n");scanf("%d",&x);pos=binSearch(a,0,N-1,x);if (pos!=-1) printf("a[%d]=%d\n",pos,x);else printf("Not found!\n");return 0;
}

4.返回表中最大数所在的结点地址

/*
已知带头结点的单链表结构定义同实验3，假设链表中所有结点值均不相同，
请编写一个递归函数linklist max(linklist head)，返回表中最大数所在的结点地址，若链表为空，返回NULL。
*/#include "slnklist.h"
/*请将本函数补充完整，并进行测试*/
linklist max(linklist head)
{linklist m;if (head->next==NULL)return NULL;elseif (head->next->next==NULL)return head->next;else{m=max(head->next);return head->next->info > m->info ? head->next:m;}
}
int main()
{   linklist head,p;head=creatbyqueue();print(head);p=max(head);if (p)printf("max=%d\n",p->info);elseprintf("链表为空\n");return 0;
}