《数据结构》实验报告专业惠普测试班级142姓名李斌学号1408090221学期 3指导老师刘勇成绩：教师评语：数据结构上机实验报告学号：1408090221 姓名：李斌所在系：惠普测试班级：142实验名称：线性结构基本算法的实现实验日期实验指导教师刘勇实验机房------------------------------------------------------------------------------------------------------1.实验目的：(1)掌握线性表顺序存储结构的基本操作：插入、删除、查找；(2)掌握线性表链式结构的基本操作：插入、删除、合并等运算；（3）掌握栈和队列基本运算的算法；（4）掌握稀疏矩阵的压缩存储的算法。

2. 实验内容：（1）实现顺序表的创建、插入、删除和查找的操作；（2）实现单链表插入、删除、合并的操作；（3）实现2个有序线性表的合并；（4）利用顺序栈实现括号匹配的算法；（5）实现顺序队列各种基本运算的算法；（6）实现链栈各种基本运算的算法；（选做）（7）实现链队列各种基本运算的算法；（选做）（8）实现稀疏矩阵压缩存储的算法。

3．算法设计（编程思路或流程图或源代码）内容：1、顺序表的插入和删除2、有序单链表的合并3、数制转换的算法实现1.//顺序表的插入和删除#include<stdio.h>//#include<stdlib.h>#include<malloc.h>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int ElemType;typedef int Status;typedef struct{ElemType *elem;int length;int listsize;}SqList;Status InitList_Sq(SqList *L){// printf("test~~\n");L->elem =(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L->elem) return OVERFLOW;L->length=0;L->listsize=LIST_INIT_SIZE;return OK;}Status CreatList_Sq(SqList *L,int n){int i;L->length=n;//printf("请输入%d个整数:",n);//3for(i=0;i<n;i++){printf("请输入第%d个整数: ",i+1);//4 i+1scanf("%d",&L->elem[i]);}return OK;}void TraverList_Sq(SqList *L){int i;printf("顺序表的长度为：%d\n",L->length);printf("顺序表中的元素依次为：");for(i=0;i<L->length;i++){printf("%5d",L->elem[i]);}printf("\n");}int ListInsert_Sq(SqList *L,int i,int e){int *newbase,*q,*p;if(i<1||i>L->length+1){printf("由于插入位置不合法导致插入操作失败\n");return ERROR;}else{if(L->length>=L->listsize){newbase=(int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(int));if(!newbase)return OVERFLOW;L->elem=newbase;L->length=+LISTINCREMENT;}q=&(L->elem[i-1]);for(p=&L->elem[L->length];p>=q;p--)*(p+1)=*p;*q=e;++L->length;return OK;}}int DeleteList_Sq(SqList *L,int i,int e){int x,*q,*p;if(i<1||i>L->length){printf("由于删除位置不合法无法进行删除\n");return ERROR;}else if(L->length==0){printf("由于是空表无法删除\n");return OVERFLOW;}else{q=&(L->elem[i-1]);e=L->elem[i-1];printf("第%d个元素%d已删除\n",i,e);for(p=&(L->elem[L->length-1]);q<p;++q)*q=*(q+1);--L->length;return OK;}}int main(){SqList a,*l=&a;//1、野指针操作// SqList *l = NULL;//这样也不行！！！空指针操作int select,n,i,x,m,b;do{printf("\n第一次使用初始化\n");printf("1 初始化\n");printf("2 顺序表的创建\n");printf("3 顺序表的插入\n");printf("4 顺序表的删除\n");printf("5 顺序表的遍历\n");printf("0 退出\n\n");printf("请选择操作1-5: ");scanf("%d",&select);switch(select){case 1:{// printf("test~~\n");if(!InitList_Sq(l)) printf("顺序表初始化失败\n"); // printf("test~~\n");InitList_Sq(l);printf("顺序表已经初始化\n");break;}case 2:{printf("请输入要创建的顺序表的长度：");scanf("%d",&n);//2 是&nCreatList_Sq(l,n);TraverList_Sq(l);break;}case 3:{printf("请输入要插入的位置：");scanf("%d",&i);//5 &iprintf("请输入要插入的元素：");scanf("%d",&x);ListInsert_Sq(l,i,x);TraverList_Sq(l);break;}case 4:{printf("请输入要删除的位置：");scanf("%d",&m);DeleteList_Sq(l,m,b);TraverList_Sq(l);break;}case 5:{TraverList_Sq(l);break;}}}while(select<=5&&select>=1);return 0;}2.#include<stdio.h>#include<stdlib.h>typedef struct node{int data;struct node *next;}node,*list;void init(list &head){head = (list)malloc(sizeof(node));head->next = NULL;}void input(list &h){list p,q;q = h;printf("输入数据的个数：");int n;scanf("%d",&n);printf("请输入%d个有序递增的数据",n);for(int i=0; i<n; i++){p = (list)malloc(sizeof(node));scanf("%d",&p->data);p->next = q->next;q->next = p;q = p;}}void output(list h){list p;p = h->next;printf("输出数据\n");while(p!=NULL){printf("%d ",p->data);p = p->next;}}void combine(list &a,list &b,list &c){list p,q,t;p = a->next;q = b->next;free(b);b = q;c = a;a = p;c->next = NULL;while(p&&q){if(p->data <= q->data){a = a->next;p->next = c->next;c->next = p;p = a;}else{b = q->next;q->next = c->next;c->next = q;q = b;}}if(p!=NULL){while(p){a = a->next;p->next = c->next;c->next = p;p = a;}}if(q!=NULL){while(q){b = q->next;q->next = c->next;c->next = q;q = b;}}}int main(){list a,b,c;init(a);init(b);printf("输入链表A:\n");input(a);printf("输入链表B:\b");input(b);combine(a,b,c);output(c);return 0;}3.#include <stdio.h>void fun(int x,int k);//x -> k进制int main(){int n;printf("你要测试几组数据? ");scanf("%d", &n);printf("请输入%d组数据(输入格式:a b):\n",n);int i,k,x;for(i = 0;i < n;++i){scanf("%d %d", &x,&k);printf("十进制数%d的%d进制表示是:",x,k);fun(x,k);printf("\n");}return 0;}void fun(int x,int k){int a,b,c = 0,zu[10] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};b = x;//do{a =b % k;zu[c] = a;c++;b = b/k;//}while(b > 0);for(--c;c>=0;--c){if(zu[c] !=-1&&zu[c] >9){printf("%c",zu[c]+('A'-10));}else{printf("%d",zu[c]);}}}4．程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。