實驗1 單連結清單
| 成績 |
實驗類型：●驗證性實驗 ○綜合性實驗 ○設計性實驗
一、實驗目的或任務
通過指導學生上機實踐，對常用資料結構的基本概念及其不同的實作方法的理論得到進一步的掌握，并對在不同存儲結構上實作不同的運算方式和技巧有所體會。
二、實驗教學基本要求
1.了解實驗目的及實驗原理；
2.編寫程式，并附上程式代碼和結果圖；
3.總結在程式設計過程中遇到的問題、解決辦法和收獲。
三、實驗教學的内容或要求
1.編寫函數,實作随機産生或鍵盤輸入一組元素,建立一個帶頭結點的單連結清單(無序)
2.編寫函數,實作周遊單連結清單
3.編寫函數,實作把單向連結清單中元素逆置
4.編寫函數,建立一個非遞減有序單連結清單
5.編寫函數,利用以上算法，建立兩個非遞減有序單連結清單,然後合并成一個非遞減連結清單。
6.編寫函數,在非遞減有序單連結清單中插入一個元素使連結清單仍然有序
7.編寫函數,實作在非遞減有序連結清單中删除值為x的結點
8.編寫一個主函數,在主函數中設計一個簡單的菜單,分别調試上述算法
四、實驗内容
實驗總結：
這是我們第一次進行資料結構實驗，在這個實驗中我體會到了很多，深刻體會到了算法的重要性，同時我們在做好上課聽講之後我們更應該下來自己多多敲代碼練習，這樣才能夠更好的掌握。關于單連結清單的建立比順序表更難懂，單連結清單的建立有頭插法和尾插法兩種，尾插法較為簡單，一定要熟練使用。
實驗結果：
實驗代碼：
#define _CRT_SECURE_NO_WARNINGS
#include
#include
typedef struct Node
{
int data;
struct Node*next;
}Node, *LinkList;
void InitList(LinkList *L) {
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
}
void CreateList(LinkList L)//建立單連結清單
{
Node *s;
int c;
scanf("%d", &c);
while (c) {
s = (LinkList)malloc(sizeof(Node));
s->data = c;
s->next = L->next;
L->next = s;
scanf("%d", &c);
}
}
void Print(LinkList L)//輸出并周遊單連結清單
{
Node* p;
p = L->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void NiZhi(LinkList L)//逆置單連結清單
{
LinkList p, s;
p = L->next;
L->next = NULL;
while (p) {
s = p;
p = p->next;
s->next = L->next;
L->next = s;
}
}
void FeiDiJian(LinkList L, int x)//建立非遞減有序單連結清單
{
LinkList p, s;
s = (LinkList)malloc(sizeof(LinkList));
s->data = x;
p = L;
while (p->next&&p->next->data <= x) {
p = p->next;
s->next = p->next;
p->next = s;
}
}
void FeiDiJian2(LinkList L) {
int x;
L = (LinkList)malloc(sizeof(LinkList));
L->next = NULL;
printf("建立非遞減有序單連結清單，随即輸入一組資料并以0結束：\n");
scanf("%d", &x);
while (x) {
FeiDiJian(L, x);
scanf("%d", &x);
}
}
void ChaRu(LinkList La, LinkList Lb, LinkList Lc)//插入一個值在單連結清單裡面
{
LinkList p, q, s, rear;
p = La->next;
q = Lb->next;
Lc = rear = La;
free(Lb);
while (p&&q) {
if (p->data < q->data) {
s = p;
p = p->next;
}
else {
s = q;
q = q->next;
}
rear->next = s;
rear = rear->next;
}
if (p) {
rear->next = p;
}
else rear->next = q;
}
void ShanChu(LinkList L, int x)//删除一個值但是不影響順序
{
LinkList p, q;
q = L->next;
p = L;
while (q&&q->data != x) {
p = q;
q = q->next;
}
if (!q) {
printf("not deleted");
}
else {
p->next = q->next;
free(q);
}
}
void Menu()
{
printf("======================================================\n");
printf("1.随機輸入一組資料，建立無序單連結清單，以0結束\n");
printf("2.以輸出的形式周遊單連結清單\n");
printf("3.把單連結清單中的元素逆置\n");
printf("4.建立一個非遞減有序單連結清單\n");
printf("5.建立兩個非遞減有序單連結清單，然後合并成一個非遞減單連結清單\n");
printf("6.在非遞減有序單連結清單中插入一個元素\n");
printf("7.删除指定的元素\n");
printf("======================================================\n");
}
void main() {
LinkList La, Lb, Lc;
InitList(&La);
InitList(&Lb);
InitList(&Lc);
int x;
int n = 0;
while (1) {
Menu();
printf("請選擇：");
scanf("%d", &n);
switch (n)
{
case 1:
printf("請輸入一組元素以建立單連結清單，以0結束：");
CreateList(La);
break;
case 2:
printf("單連結清單以輸出形式周遊為：");
Print(La);
break;
case 3:
NiZhi(La);
printf("已建立單連結清單中的元素逆置為：");
Print(La);
break;
case 4:
FeiDiJian2(La);
printf("所建非遞減有序單連結清單為：");
Print(La);
break;
case 5:
FeiDiJian2(La);
FeiDiJian2(Lb);
ChaRu(La, Lb, Lc);
printf("合并後的單連結清單為：");
Print(Lc);
break;
case 6:
FeiDiJian2(La);
printf("建立非遞減有序單連結清單為：");
Print(La);
printf("請輸入要插入單連結清單的元素x: ");
scanf("%d", &x);
FeiDiJian(La, x);
Print(La);
break;
case 7:
FeiDiJian2(La);
printf("建立非遞減有序單連結清單為：");
Print(La);
printf("請輸入要删除的元素x：");
scanf("%d", &x);
ShanChu(La, x);
Print(La);
break;
default:printf("輸入有誤，請重新選擇！\n");
}
}
}
摘要