数据结构实验报告一．顺序表要求：实现顺序表的初始化、在指定位置插入和删除元素。

算法思路：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

顺序表的初始化操作就是为顺序表分配一个预定义大小的空间，并将线性表的当前长度设为“0”。

线性表的插入操作是在线性表的第i-1个数据元素和第i个元素之间插入新的数据元素，使得长度为n的线性表变成长度为n+1的线性表，而删除恰好相反长度变为n-1的线性表，而且删除点后面的元素要往前移动一个位。

程序代码：#include <stdio.h>#include <malloc.h>#define MAXSIZE 50typedef char elemtype;typedef struct //类型定义{ elemtype v[MAXSIZE];int last;}SeqList;SeqList *Init_SeqList() //初始化操作{SeqList *L;L=(SeqList*)malloc(sizeof(SeqList));L->last=-1;return L;}void Create(SeqList *L) //建立顺序表{int i=0;elemtype ch;scanf("%c",&ch);while(ch!='\n'){L->v[i++]=ch;scanf("%c",&ch);L->last=i-1;}}void PrintL(SeqList *L) //输出顺序表{int i;printf("此表为:\n");for(i=0;i<L->last;i++){printf("%c",L->v[i]);}printf("%c\n",L->v[i]);}void Length(SeqList *L) //顺序表长度函数{printf("此表长度:\n%d",L->last+1);printf("\n");}void insert(SeqList *L,int i,elemtype x) //插入函数{int j;if(L->last==0)printf("Error!\n");if(i<1||i>L->last)printf("Error!");for(j=L->last;j>=i-1;j--)L->v[j+1]=L->v[j];L->v[i-1]=x;L->last++;PrintL(L);Length(L);}void Delete(SeqList *L,int i) //删除函数{int j;if(L->last==-1)printf("Error!");if(i<1||i>L->last+1)printf("Error!");for(j=i;j<=L->last;j++)L->v[j-1]=L->v[j];L->last--;PrintL(L);Length(L);}void main() //程序主函数{int i,j,k;elemtype a,b;SeqList *L;L=Init_SeqList();printf("建立顺序表：\n");Create(L);PrintL(L);Length(L) ;printf("\n");printf("请输入你想插入的元素及其位置：\n");scanf("%s %d",&b,&j);insert(L,j,b);printf("请输入你想删除的位置：\n");scanf("%d",&k);Delete(L,k);}程序运行：二．单链表要求：实现单链表的初始化、在指定位置插入和删除元素。

算法思路：线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。

因此，为了表现每个元素与后继元素的逻辑关系需要用到指针。

单链表的插入就是先生成一个数据域为插入元素的界点然后插入单链表中，并且修改前后节点的指针域，完成插入操作。

反之删除链表元素时仅需修改前后两个元素的节点使之相连便可。

程序代码：#define NULL 0#include "stdlib.h"#include"stdio.h"typedef struct LNode{int data;struct LNode *next;} LNode, *LinkList;void CreateList_L( LinkList *L);void ShowList(LinkList *L);LNode *GetElem(LinkList head);void InsertList(LinkList *head);void DeleteList(LinkList head);void main(){ LNode *L;int j,loop=1;printf("\n");while(loop){printf("1.建立单链表\n");printf("2.在单链表插入元素\n");printf("3.删除单链表元素\n");printf("请选择序号(1-3): ");scanf("%d",&j);switch(j){case 1:CreateList_L(&L);break;case 2:InsertList(&L);break;case 3:DeleteList(L);break;}printf("结束此程序吗？（0——结束1——继续）：\n");scanf("%d",&loop);printf("\n");}}void CreateList_L( LinkList *L){ LNode *p;int flag=1;(*L)=(LinkList)malloc(sizeof(LNode));(*L)->next=NULL;printf("请输入链表元素(输0 结束):\n");while(flag){p=(LinkList)malloc(sizeof(LNode));p->next=NULL;scanf("%d",&p->data);if (p->data==0)break;p->next=(*L)->next;(*L)->next=p;}ShowList(L);}void ShowList(LinkList *L){LinkList p;printf("头节点-> ");for(p=(*L)->next;p!=NULL;p=p->next){printf("%d -> ",p->data);}printf("NULL !\n");}void InsertList(LinkList *head){LNode *pre,*s;int i,j,x;printf("请输入插入位置:");scanf("%d",&i);printf("请输入插入元素:");scanf("%d",&x);pre=*head;j=0;while (pre!=NULL && j<i-1){pre=pre->next; j++;}s=(LNode *)malloc(sizeof(LNode));s->data=x;s->next=pre->next;pre->next=s;ShowList(head);printf("\n");}void DeleteList(LinkList head) {LNode *pre,*r;int i,j;pre=head;printf("请输入删除位置:");scanf("%d",&i);j=0;/*查找第i-1个结点*/while(pre->next!=NULL && j<i-1) {pre=pre->next; j++; }r=pre->next;pre->next=r->next ;free(r);ShowList(&head);}程序运行：三．链表的合并要求：给定的2个有序线性链表的合并（合并到1个新的链表中以及合并到其中的1个链表中两种方式）。

算法思路：先创建两个有序线性链表a，b。

然后将两个有序线性链表a，b合并到a或者h 中，得运用指针分别指向a，b当前待比较插入的节点，最后将两个链表的元素有序归并到表a或者h中。

程序代码：#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<malloc.h>#define L sizeof(struct Node)struct Node{long int number;struct Node *next;};struct Node *create(int a){int n;struct Node *p1, *p2, *head;head = NULL;n = 0;p2 = p1 = (struct Node *) malloc(L);scanf("%ld", &p1->number);while (a){n = n + 1;if (n == 1)head = p1;elsep2->next = p1;p2 = p1;p1 = (struct Node *) malloc(L);if (a != 1)scanf("%ld", &p1->number);a--;}p2->next = NULL;return (head);}void print(struct Node *head){struct Node *p;p = head;printf("数字:\n");if (head != NULL)do{printf("%ld", p->number);printf(" ");p = p->next;} while (p != NULL);printf("\n");}struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b) { int temp;struct Node *head, *p1, *p2, *pos;if (a >= b) {head = p1 = chain1;p2 = chain2;} else/*b>a*/ {head = p1 = chain2;p2 = chain1;temp = a, a = b, b = temp;}pos = head;while (p2 != NULL) {p1 = p1->next;pos->next = p2;pos = p2;p2 = p2->next;pos->next = p1;pos = p1;}return head;}void InsertSort(struct Node *p, int m){int i, j, t;struct Node *k;k = p;for (i = 0; i < m - 1; i++) {for (j = 0; j < m - i - 1; j++) {if (p->number > (p->next)->number) {t = p->number;p->number = (p->next)->number;(p->next)->number = t;}p = p->next;}p = k;}}int main(){struct Node *p1, *p2;int a;int b;int h;printf("请输入第一个链表:\n");printf("\n输入链表的长度a:\n");scanf("%d", &a);printf("请输入链表数据：");p1 = create(a);printf("\n你刚才输入的第一个链表信息:\n ");print(p1);printf("\n 请输入第二个链表:\n");printf("\n输入链表的长度b:\n");scanf("%d", &b);printf("请输入链表数据：");p2 = create(b);printf("\n你刚才输入的第二个链表的信息:\n");print(p2);p1 = inter_link(p1, a, p2, b);h = a + b;a = h;print(p1);InsertSort(p1, h);InsertSort(p1, a);printf("\n排序后的链表a:\n");print(p1);printf("\n排序后的链表h:\n");print(p1);return 0;}程序运行：四．双向链表要求：实现双向链表的初始化、在指定位置插入和删除元素。