文章目錄

• 線性表——鍊式存儲
• • • 源代碼

線性表——鍊式存儲

源代碼

#include "stdio.h"
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存儲空間初始配置設定量 */
typedef int Status;/* Status 是函數的類型,其值是函數結果狀态代碼，如 OK 等 */
typedef int ElemType;/* ElemType 類型根據實際情況而定，這裡假設為 int */
Status visit(ElemType c) {
	printf("%d ",c);
	return OK;
}
typedef struct Node {
	ElemType data;
	struct Node *next;
} Node;
typedef struct Node *LinkList; /* 定義 LinkList */
/* 初始化順序線性表 */
Status InitList(LinkList *L) {
	*L=(LinkList)malloc(sizeof(Node)); /* 産生頭結點,并使 L 指向此頭結點 */
	if(!(*L)) /* 存儲配置設定失敗 */
		return ERROR;
	(*L)->next=NULL; /* 指針域為空 */
	return OK;
}
/* 初始條件：順序線性表 L 已存在。操作結果：若 L 為空表，則傳回 TRUE，否則傳回 FALSE
*/
Status ListEmpty(LinkList L) {
	if(L->next)
		return FALSE;
	else
		return TRUE;
}
/* 初始條件：順序線性表 L 已存在。操作結果：将 L 重置為空表 */
Status ClearList(LinkList *L) {
	LinkList p,q;
	p=(*L)->next; /* p 指向第一個結點 */
	while(p) { /* 沒到表尾 */
		q=p->next;
		free(p);
		p=q;
	}
	(*L)->next=NULL; /* 頭結點指針域為空 */
	return OK;
}
/* 初始條件：順序線性表 L 已存在。操作結果：傳回 L 中資料元素個數 */
int ListLength(LinkList L) {
	int i=0;
	LinkList p=L->next; /* p 指向第一個結點 */
	while(p) {
		i++;
		p=p->next;
	}
	return i;
}
/* 初始條件：順序線性表 L 已存在，1≤i≤ListLength(L) */
/* 操作結果：用 e 傳回 L 中第 i 個資料元素的值 */
Status GetElem(LinkList L,int i,ElemType *e) {
	int j;
	LinkList p;  /* 聲明一結點 p */
	p = L->next;  /* 讓 p 指向連結清單 L 的第一個結點 */
	j = 1; /* j 為計數器 */
	while (p && j<i) { /* p 不為空或者計數器 j 還沒有等于 i 時，循環繼續 */
		p = p->next; /* 讓 p 指向下一個結點 */
		++j;
	}
	if ( !p || j>i )
		return ERROR; /* 第 i 個元素不存在 */
	*e = p->data; /* 取第 i 個元素的資料 */
	return OK;
}
/* 初始條件：順序線性表 L 已存在 */
/* 操作結果：傳回 L 中第 1 個與 e 滿足關系的資料元素的位序。 */
/* 若這樣的資料元素不存在，則傳回值為 0 */
int LocateElem(LinkList L,ElemType e) {
	int i=0;
	LinkList p=L->next;
	while(p) {
		i++;
		if(p->data==e) /* 找到這樣的資料元素 */
			return i;
		p=p->next;
	}
	return 0;
}
/* 初始條件：順序線性表 L 已存在,1≤i≤ListLength(L)， */
/* 操作結果：在 L 中第 i 個位置之前插入新的資料元素 e，L 的長度加 1 */
Status ListInsert(LinkList *L,int i,ElemType e) {
	int j;
	LinkList p,s;
	p = *L;
	j = 1;
	while (p && j < i) { /* 尋找第 i 個結點 */
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR; /* 第 i 個元素不存在 */
	s = (LinkList)malloc(sizeof(Node)); /* 生成新結點(C 語言标準函數) */
	s->data = e;
	s->next = p->next; /* 将 p 的後繼結點指派給 s 的後繼 */
	p->next = s; /* 将 s 指派給 p 的後繼 */
	return OK;
}
/* 初始條件：順序線性表 L 已存在，1≤i≤ListLength(L) */
/* 操作結果：删除 L 的第 i 個資料元素，并用 e 傳回其值，L 的長度減 1 */
Status ListDelete(LinkList *L,int i,ElemType *e) {
	int j;
	LinkList p,q;
	p = *L;
	j = 1;
	while (p->next && j < i) { /* 周遊尋找第 i 個元素 */
		p = p->next;
		++j;
	}
	if (!(p->next) || j > i)
		return ERROR; /* 第 i 個元素不存在 */
	q = p->next;
	p->next = q->next; /* 将 q 的後繼指派給 p 的後繼 */
	*e = q->data; /* 将 q 結點中的資料給 e */
	free(q); /* 讓系統回收此結點，釋放記憶體 */
	return OK;
}
/* 初始條件：順序線性表 L 已存在 */
/* 操作結果：依次對 L 的每個資料元素輸出 */
Status ListTraverse(LinkList L) {
	LinkList p=L->next;
	while(p) {
		visit(p->data);
		p=p->next;
	}
	printf("\n");
	return OK;
}
/* 随機産生 n 個元素的值，建立帶表頭結點的單鍊線性表 L（頭插法） */
void CreateListHead(LinkList *L, int n) {
	LinkList p;
	int i;
	srand(time(0)); /* 初始化随機數種子 */
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL; /* 先建立一個帶頭結點的單連結清單 */
	for (i=0; i<n; i++) {
		p = (LinkList)malloc(sizeof(Node)); /* 生成新結點 */
		p->data = rand()%100+1; /* 随機生成 100 以内的數字 */
		p->next = (*L)->next;
		(*L)->next = p; /* 插入到表頭 */
	}
}
/* 随機産生 n 個元素的值，建立帶表頭結點的單鍊線性表 L（尾插法） */
void CreateListTail(LinkList *L, int n) {
	LinkList p,r;
	int i;
	srand(time(0)); /* 初始化随機數種子 */
	*L = (LinkList)malloc(sizeof(Node)); /* L 為整個線性表 */
	r=*L; /* r 為指向尾部的結點 */
	for (i=0; i<n; i++) {
		p = (Node *)malloc(sizeof(Node)); /* 生成新結點 */
		p->data = rand()%100+1; /* 随機生成 100 以内的數字 */
		r->next=p; /* 将表尾終端結點的指針指向新結點 */
		r = p; /* 将目前的新結點定義為表尾終端結點 */
	}
	r->next = NULL; /* 表示目前連結清單結束 */
}
int main() {
	LinkList L;
	ElemType e;
	Status i;
	int j,k;
	i=InitList(&L);
	printf("初始化 L 後：ListLength(L)=%d\n",ListLength(L));
	for(j=1; j<=5; j++)
		i=ListInsert(&L,1,j);
	printf("在 L 的表頭依次插入 1～5 後：L.data=");
	ListTraverse(L);
	printf("ListLength(L)=%d \n",ListLength(L));
	i=ListEmpty(L);
	printf("L 是否空：i=%d(1:是 0:否)\n",i);
	i=ClearList(&L);
	printf("清空 L 後：ListLength(L)=%d\n",ListLength(L));
	i=ListEmpty(L);
	printf("L 是否空：i=%d(1:是 0:否)\n",i);
	for(j=1; j<=10; j++)
		ListInsert(&L,j,j);
	printf("在 L 的表尾依次插入 1～10 後：L.data=");
	ListTraverse(L);
	printf("ListLength(L)=%d \n",ListLength(L));
	ListInsert(&L,1,0);
	printf("在 L 的表頭插入 0 後：L.data=");
	ListTraverse(L);
	printf("ListLength(L)=%d \n",ListLength(L));
	GetElem(L,5,&e);
	printf("第 5 個元素的值為：%d\n",e);
	for(j=3; j<=4; j++) {
		k=LocateElem(L,j);
		if(k)
			printf("第%d 個元素的值為%d\n",k,j);
		else
			printf("沒有值為%d 的元素\n",j);
	}
	k=ListLength(L); /* k 為表長 */
	for(j=k+1; j>=k; j--) {
		i=ListDelete(&L,j,&e); /* 删除第 j 個資料 */
		if(i==ERROR)
			printf("删除第%d 個資料失敗\n",j);
		else
			printf("删除第%d 個的元素值為：%d\n",j,e);
	}
	printf("依次輸出 L 的元素：");
	ListTraverse(L);
	j=5;
	ListDelete(&L,j,&e); /* 删除第 5 個資料 */
	printf("删除第%d 個的元素值為：%d\n",j,e);
	printf("依次輸出 L 的元素：");
	ListTraverse(L);
	i=ClearList(&L);
	printf("\n 清空 L 後：ListLength(L)=%d\n",ListLength(L));
	CreateListHead(&L,20);
	printf("整體建立 L 的元素(頭插法)：");
	ListTraverse(L);
	i=ClearList(&L);
	printf("\n 删除 L 後：ListLength(L)=%d\n",ListLength(L));
	CreateListTail(&L,20);
	printf("整體建立 L 的元素(尾插法)：");
	ListTraverse(L);
	return 0;
}