数据结构实验

成绩

专业班级 信息131班 学号 201312030131 姓名 朱潇翔 报告日期 2015.11.10

实验类型：●验证性实验 ○综合性实验 ○设计性实验 实验目的或任务：

通过指导学生上机实践，对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。

实验教学基本要求：

1.了解实验目的及实验原理；

2.编写程序，并附上程序代码和结果图；

3.总结在编程过程中遇到的问题、解决办法和收获。 实验教学的内容或要求：

1.编写函数,实现随机产生或键盘输入一组元素,建立一个带头结点的单链表（无序）

2.编写函数,实现遍历单链表

3.编写函数,实现把单向链表中元素逆置 4.编写函数,建立一个非递减有序单链表

5.编写函数,利用以上算法，建立两个非递减有序单链表,然后合并成一个非递减链表。

6.编写函数,在非递减有序单链表中插入一个元素使链表仍然有序 7.编写函数,实现在非递减有序链表中删除值为x的结点

8.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法 实验开出要求： 必做

实验所需仪器设备：

1.计算机

2.相关软件（如C,C++,PASCAL,VC,DELPHI等等） 实验所用材料：

计算机耗材

实验内容：

1.编写函数,实现随机产生或键盘输入一组元素,建立一个带头结点的单链表（无序）

/*头插法，得到结果与输入元素顺序相反*/ #include #include typedef struct {

char data;

struct Node * next;

}Node, *LinkList;

LinkList CreateFromHead(); int main() { }

/*头插法*/

LinkList CreateFromHead() {

char c; int flag = 1; Node *s; Node *L;

L = (LinkList)malloc(sizeof(Node)); L->next = NULL; while (flag) {

c = getchar(); if (c != '\\n') {

s = (Node *)malloc(sizeof(Node)); s->data = c;

LinkList L, p; L = CreateFromHead(); p = L->next; /*输出单链表*/ do {

printf(\"->%c\", p->data); p = p->next;

} while (p != NULL); printf(\"\\n\"); system(\"pause\"); return 0;

}

}

}

s->next = L->next; L->next = s;

else { }

flag = 0;

return L;

/*尾插法，得到结果与输入元素顺序相同*/ #include #include typedef struct {

char data;

struct Node * next;

}Node, *LinkList;

LinkList CreateFromHead(); int main() { }

/*尾插法*/

LinkList CreateFromHead() {

LinkList L, p; L = CreateFromHead(); p = L->next; /*输出单链表*/ do {

printf(\"->%C\", p->data); p = p->next;

} while (p != NULL); printf(\"\\n\"); system(\"pause\"); return 0;

}

char c; int flag = 1; Node *s; Node *L, *r;

L = (LinkList)malloc(sizeof(Node)); L->next = NULL; r = L; while (flag) { } return L;

c = getchar(); if (c != '\\n') { } else { }

flag = 0; r->next = NULL;

s = (Node *)malloc(sizeof(Node)); s->data = c; r->next = s; r = s;

2.编写函数,实现遍历单链表

#include #include typedef struct {

char data;

struct Node * next;

}Node, *LinkList;

LinkList CreateFromHead(); int ListLength(LinkList L); int main() {

LinkList L, p;

}

int len;

L = CreateFromHead(); len = ListLength(L); p = L->next; /*输出单链表*/ do {

printf(\"->%c\", p->data); p = p->next;

} while (p != NULL);

printf(\"\\n此单链表的长度为：len=%d\\n\", len); system(\"pause\"); return 0;

/*尾插法*/

LinkList CreateFromHead() { }

/*通过求链表的长度遍历链表*/ int ListLength(LinkList L)

char c; int flag = 1; Node *s; Node *L, *r;

L = (LinkList)malloc(sizeof(Node)); L->next = NULL; r = L; while (flag) { } return L;

c = getchar(); if (c != '\\n') { } else { }

flag = 0; r->next = NULL;

s = (Node *)malloc(sizeof(Node)); s->data = c; r->next = s; r = s;

{ }

int len = 0; Node *p; p = L->next; while (p != NULL) { }

return len;

len++; p = p->next;

3、编写函数,实现把单向链表中元素逆置

#include #include /*建立双向链表*/ typedef struct {

LinkList CreateFromTail();

LinkList inversePermutation(LinkList L);

int main() {

LinkList L; Node *p;

L = CreateFromTail(); L = inversePermutation(L); p = L->next; /*输出单链表*/ do {

printf(\"->%c\", p->data); p = p->next; char data;

struct Node *next;

}Node, *LinkList;

} while (p != NULL); printf(\"\\n\");

}

system(\"pause\"); return 0;

/*尾插法*/

LinkList CreateFromTail() { }

/*头插法实现单链表逆置*/

LinkList inversePermutation(LinkList L) {

Node *p, *s; p = L->next; L->next = NULL; while (p != NULL) { }

s = p->next; p->next = L->next; L->next = p; p = s; char c; int flag = 1; Node *s; Node *L, *r;

L = (LinkList)malloc(sizeof(Node)); L->next = NULL; r = L; while (flag) { } return L;

c = getchar(); if (c != '\\n') { } else { }

flag = 0; r->next = NULL;

s = (Node *)malloc(sizeof(Node)); s->data = c; r->next = s; r = s;

}

return L;

4.编写函数,建立一个非递减有序单链表

#include #include /*建立单链表*/ typedef struct {

LinkList CreateFromTail(); LinkList sortAscend(LinkList L);

int main() { }

/*尾插法*/

LinkList CreateFromTail() {

char c; int flag = 1; Node *s; LinkList L; Node *p;

L = CreateFromTail(); L = sortAscend(L); p = L->next; /*输出单链表*/ do {

printf(\"->%c\", p->data); p = p->next; char data;

struct Node *next;

}Node, *LinkList;

} while (p != NULL); printf(\"\\n\"); system(\"pause\"); return 0;

}

Node *L, *r;

L = (LinkList)malloc(sizeof(Node)); L->next = NULL; r = L; while (flag) { } return L;

c = getchar(); if (c != '\\n') { } else { }

flag = 0; r->next = NULL;

s = (Node *)malloc(sizeof(Node)); s->data = c; r->next = s; r = s;

/*实现单链表元素升序排列*/ LinkList sortAscend(LinkList L) {

Node *p, *q; char ch; p = L->next;

while (p->next != NULL) { }

q = p->next; while (q != NULL) { }

p = p->next;

if (p->data > q->data) { }

q = q->next;

ch = p->data; p->data = q->data; q->data = ch;

return L;

}

5.编写函数,利用以上算法，建立两个非递减有序单链表,然后合并成一个非递减链表。

#include #include /*建立单链表*/ typedef struct {

void printLink(LinkList L); LinkList CreateFromTail(); LinkList sortAscend(LinkList L);

LinkList MergeLinkList(LinkList LA, LinkList LB);

int main() {

L = sortAscend(L);

printf(\"第一个有序单链表为:> \"); printLink(L); printf(\"\\n\");

printf(\"第二个单链表为:> \"); printLink(head); printf(\"\\n\");

printf(\"第一个单链表为:> \"); printLink(L); printf(\"\\n\");

L = CreateFromTail(); head = CreateFromTail(); LinkList L, head; char data;

struct Node *next;

}Node, *LinkList;

}

head = sortAscend(head);

printf(\"第二个有序单链表为:> \"); printLink(head); printf(\"\\n\");

L = MergeLinkList(L, head); printf(\"合并后有序单链表为:> \"); printLink(L); printf(\"\\n\"); system(\"pause\"); return 0;

/*输出单链表*/

void printLink(LinkList L) { }

/*尾插法*/

LinkList CreateFromTail() {

char c; int flag = 1; Node *s; Node *L, *r;

L = (LinkList)malloc(sizeof(Node)); L->next = NULL; r = L; while (flag) {

c = getchar(); if (c != '\\n') { }

s = (Node *)malloc(sizeof(Node)); s->data = c; r->next = s; r = s;

Node *p; p = L->next; while (p != NULL) { }

printf(\"->%c\", p->data); p = p->next;

}

}

else { }

flag = 0; r->next = NULL;

return L;

/*实现单链表元素升序排列*/ LinkList sortAscend(LinkList L) { }

/*合并有序单链表*/

LinkList MergeLinkList(LinkList LA, LinkList LB) {

LinkList LC; Node *pa, *pb, *pc; pa = LA->next; pb = LB->next; LC = LA;

LC->next = NULL; pc = LC;

while (pa != NULL&&pb != NULL) {

if (pa->data <= pb->data) Node *p, *q; char ch; p = L->next;

while (p->next != NULL) { } return L;

q = p->next; while (q != NULL) { }

p = p->next;

if (p->data > q->data) { }

q = q->next;

ch = p->data; p->data = q->data; q->data = ch;

}

}

{ } else { }

pc->next = pb; pc = pb; pb = pb->next; pc->next = pa; pc = pa; pa = pa->next;

if (pa != NULL) { } else { } free(LB); return LC;

pc->next = pb; pc->next = pa;

6.编写函数,在非递减有序单链表中插入一个元素使链表仍然有序

#include #include /*建立单链表*/ typedef struct {

void printLink(LinkList L); LinkList CreateFromTail();

char data;

struct Node *next;

}Node, *LinkList;

LinkList sortAscend(LinkList L);

LinkList MergeCreateLink(LinkList L, char ch);

int main() { }

/*输出单链表*/

void printLink(LinkList L) { }

/*尾插法*/

LinkList CreateFromTail() {

char c; int flag = 1; Node *p; p = L->next; while (p != NULL) { }

printf(\"->%c\", p->data); p = p->next; system(\"pause\"); return 0;

printf(\"请输入要插入的元素:> \"); ch = getchar();

L = MergeCreateLink(L, ch); printf(\"有序单链表为:> \"); printLink(L); printf(\"\\n\"); L = sortAscend(L);

printf(\"有序单链表为:> \"); printLink(L); printf(\"\\n\");

L = CreateFromTail(); printf(\"单链表为:> \"); printLink(L); printf(\"\\n\"); LinkList L; char ch;

}

Node *s; Node *L, *r;

L = (LinkList)malloc(sizeof(Node)); L->next = NULL; r = L; while (flag) { } return L;

c = getchar(); if (c != '\\n') { } else { }

flag = 0; r->next = NULL;

s = (Node *)malloc(sizeof(Node)); s->data = c; r->next = s; r = s;

/*实现单链表元素升序排列*/ LinkList sortAscend(LinkList L) {

Node *p, *q; char ch; p = L->next;

while (p->next != NULL) { }

q = p->next; while (q != NULL) { }

p = p->next;

if (p->data > q->data) { }

q = q->next;

ch = p->data; p->data = q->data; q->data = ch;

}

return L;

/*在有序单链表中插入元素*/

LinkList MergeCreateLink(LinkList L,char ch) { }

Node *p, *q, *s; p = L; q = p->next;

s = (Node *)malloc(sizeof(Node)); s->data = ch;

while ((q != NULL) && (q->data < ch)) { }

s->next = p->next; p->next = s; return L;

p = p->next; q = p->next;

7.编写函数,实现在非递减有序链表中删除值为x的结点

#include #include /*建立单链表*/ typedef struct {

void printLink(LinkList L); LinkList CreateFromTail(); LinkList sortAscend(LinkList L);

LinkList MergeDeleteLink(LinkList L, char ch);

int main() {

LinkList L; char data;

struct Node *next;

}Node, *LinkList;

}

char ch;

L = CreateFromTail(); printf(\"单链表为:> \"); printLink(L); printf(\"\\n\"); L = sortAscend(L);

printf(\"有序单链表为:> \"); printLink(L); printf(\"\\n\");

printf(\"请输入您要删除的元素:> \"); ch = getchar();

L = MergeDeleteLink(L, ch); printf(\"删除后有序单链表为:> \"); printLink(L); printf(\"\\n\"); system(\"pause\"); return 0;

/*输出单链表*/

void printLink(LinkList L) { }

/*尾插法*/

LinkList CreateFromTail() {

char c; int flag = 1; Node *s; Node *L, *r;

L = (LinkList)malloc(sizeof(Node)); L->next = NULL; r = L; while (flag) Node *p; p = L->next; while (p != NULL) { }

printf(\"->%c\", p->data); p = p->next;

}

{ } return L;

c = getchar(); if (c != '\\n') { } else { }

flag = 0; r->next = NULL;

s = (Node *)malloc(sizeof(Node)); s->data = c; r->next = s; r = s;

/*实现单链表元素升序排列*/ LinkList sortAscend(LinkList L) { }

/*删除有序单链表中的某个元素*/

LinkList MergeDeleteLink(LinkList L, char ch) {

Node *p, *q, *s; Node *p, *q; char ch; p = L->next;

while (p->next != NULL) { } return L;

q = p->next; while (q != NULL) { }

p = p->next;

if (p->data > q->data) { }

q = q->next;

ch = p->data; p->data = q->data; q->data = ch;

}

int flag = 0; p = L; q = p->next; while (q != NULL) { }

if (flag == 0)

printf(\"没找到您要删除的元素！\\n\"); return L;

if (q->data == ch) { } else { }

q = q->next;

p = p->next; flag = 1;

p->next = q->next;

8.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法

#include #include

typedef struct {

char data;

struct Node * next;

}Node, *LinkList;

void meau();

LinkList CreateFromHead(); void ListLength(LinkList L); void printLink(LinkList L);

LinkList inversePermutation(LinkList L); LinkList sortAscend(LinkList L);

LinkList MergeLinkList(LinkList LA, LinkList LB); LinkList MergeCreateLink(LinkList L, char ch); LinkList MergeDeleteLink(LinkList L, char ch);

int main() {

int inter; do {

meau();

printf(\"请输入您要执行的功能:> \"); scanf_s(\"%d\", &inter); switch (inter) {

case 1: { } case 2: { } case 3: { } case 4: {

L = sortAscend(L); printLink(L); break;

L = inversePermutation(L); printLink(L); break;

ListLength(L); break;

LinkList L,head;

printf(\"请输入您要插入的单链表 L 的元素:> \"); L = CreateFromHead();

}

}

}

printf(\"请输入您要插入的单链表 head 的元素:> \"); getchar();

/*消除回车的影响*/

head = CreateFromHead(); L = MergeLinkList(L, head); printLink(L); break;

case 5: { } case 6: { } case 0: { } default: { }

printf(\"请输入正确的功能编号！\\n\"); break;

printf(\"感谢使用本系统，欢迎您的下次使用！\\n\"); break;

printf(\"请输入您要删除的元素:> \"); char ch;

getchar(); /*消除回车的影响*/ ch = getchar();

L = MergeDeleteLink(L, ch); printLink(L); break;

printf(\"请输入您要插入的元素:>\"); char ch; getchar();

/*消除回车的影响*/

ch = getchar();

L = MergeCreateLink(L, ch); printLink(L); break;

} while (inter);

system(\"pause\"); return 0;

void meau() { }

/*输出单链表*/

void printLink(LinkList L) { }

/*尾插法*/

LinkList CreateFromHead() {

char c; int flag = 1; Node *s; Node *L, *r;

L = (LinkList)malloc(sizeof(Node)); L->next = NULL; r = L; while (flag) {

c = getchar(); if (c != '\\n') {

s = (Node *)malloc(sizeof(Node)); s->data = c; r->next = s;

Node *p; p = L->next;

printf(\"执行完后单链表为:> \"); while (p != NULL) { }

printf(\"\\n\");

printf(\"->%c\", p->data); p = p->next;

printf(\"1、单链表遍历，求链表长度\\n\"); printf(\"2、单链表元素逆置\\n\"); printf(\"3、建立非递减有序单链表\\n\"); printf(\"4、合并成非递减链表\\n\");

printf(\"5、在非递减有序单链表中插入元素\\n\"); printf(\"6、在非递减有序链表中删除值为x的结点\\n\"); printf(\"0、退出系统\\n\");

}

}

}

r = s;

else { }

flag = 0; r->next = NULL;

return L;

/*通过求链表的长度遍历链表*/ void ListLength(LinkList L) { }

/*头插法实现单链表逆置*/

LinkList inversePermutation(LinkList L) { }

/*实现单链表元素升序排列*/ LinkList sortAscend(LinkList L) {

Node *p, *s; p = L->next; L->next = NULL; while (p != NULL) { } return L;

s = p->next; p->next = L->next; L->next = p; p = s; int len = 0; Node *p; p = L->next; while (p != NULL) { }

printf(\"\\n此单链表的长度为：len=%d\\n\", len);

len++; p = p->next;

}

Node *p, *q; char ch; p = L->next;

while (p->next != NULL) { } return L;

q = p->next; while (q != NULL) { }

p = p->next;

if (p->data > q->data) { }

q = q->next;

ch = p->data; p->data = q->data; q->data = ch;

/*合并有序单链表*/

LinkList MergeLinkList(LinkList LA, LinkList LB) {

LinkList LC; Node *pa, *pb, *pc; pa = LA->next; pb = LB->next; LC = LA;

LC->next = NULL; pc = LC;

while (pa != NULL&&pb != NULL) {

if (pa->data <= pb->data) { } else {

pc->next = pb; pc = pb; pb = pb->next; pc->next = pa; pc = pa; pa = pa->next;

}

}

}

if (pa != NULL) { } else { } free(LB); sortAscend(LC); return LC;

pc->next = pb; pc->next = pa;

/*在有序单链表中插入元素*/

LinkList MergeCreateLink(LinkList L, char ch) { }

/*删除有序单链表中的某个元素*/

LinkList MergeDeleteLink(LinkList L, char ch) {

Node *p, *q, *s; int flag = 0; p = L; q = p->next; while (q != NULL) {

if (q->data == ch) {

Node *p, *q, *s; p = L; q = p->next;

s = (Node *)malloc(sizeof(Node)); s->data = ch;

while ((q != NULL) && (q->data < ch)) { }

s->next = p->next; p->next = s; return L;

p = p->next; q = p->next;

}

}

}

flag = 1;

p->next = q->next;

else { }

q = q->next;

p = p->next;

if (flag == 0)

printf(\"没找到您要删除的元素！\\n\"); return L;