線性表2：連結清單的基本操作

鍊式存儲結構【連結清單】的增 删 改 查 逆序輸出 排序linkSeqlist

• 連結清單的特點
• 連結清單的描述
• 基本操作
• • 建立空連結清單
  • 第一種插入方式：頭插
  • 輸對外連結表
  • 求表長
  • 查
  • 第二種插入方式：任意位置插入新結點
  • 删
• 逆序輸出
• 排序
• 清空
• 銷毀

此系列文主要用于自查、複習。是以行文、邏輯、思路是按照個人的思考方式來的，但也希冀能幫到一二三位初學者。

線性表的特點：

1.表頭無前驅，表尾無後繼

2.其他元素有且僅有一個直接前驅和一個直接後繼

線性表有順序存儲結構和鍊式存儲結構，下面介紹鍊式存儲結構的單向連結清單。

連結清單的特點

優點： 删除和增加不會造成大量資料的移動

缺點： 查找、修改比較麻煩

連結清單的描述

描述： 資料域+指針域

typedef int datatype;

typedef struct node {
	datatype data;//資料域
	struct node * next;//儲存下一個資料的位址
}linknode, * linklist;
           

基本操作

建立空連結清單

用malloc動态申請空間

linklist createLinkList()
{
	//1.申請頭結點的空間
	linklist H = (linklist)malloc(sizeof(linknode));
	if(NULL == H)
	{
		printf("建立頭結點失敗\n");
		return NULL;
	}
	
	//2.給頭結點指派
	H->data = 0;
	H->next = NULL;
	
	//3.傳回頭節點
	return H;
}
           

第一種插入方式：頭插

頭插，新結點永遠插入第一項（頭結點不是第一項，頭結點後面才是第一項）

int headInsertLinkList(linklist H, datatype x)
{
	//1.申請新結點空間
	linklist pnew = (linklist)malloc(sizeof(linknode));
	if(NULL == pnew)
	{
		printf("申請新結點失敗\n");
		return -1;
	}

	//2.給新結點指派
	pnew->data = x;
	
	//3.新結點先儲存頭結點下一個資料的位址
	pnew->next = H->next;
	//4.将新結點接入頭結點後面
	H->next = pnew;

	return 0;
}
           

輸對外連結表

void showLinkList(linklist H)
{
	linklist p = H->next;

	while(p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}
           

求表長

int linkLength(linklist H)
{
	linklist p = H;
	int length = 0;
	
	while(p->next != NULL)
	{
		p = p->next;
		length++;
	}
	
	return length;
}
           

查

單連結清單中，取第i個元素必須從頭結點出發尋找。

按位置查找，查找第pos項元素，傳回其位址

linklist searchPos(linklist H, int pos)
{
	int count = -1;//計數：記錄周遊的次數
	linklist p = H;
	int length = linkLength(H);
	
	if(pos<0 || pos>length)//1.判斷位置是否合法
	{
		printf("位置不在表長範圍内\n");
		return NULL;
	}
	
	//2.依次周遊直到pos
	while(count < pos)
	{
		p = p->next;
		count++;
	}
	
	return p;
}
           

第二種插入方式：任意位置插入新結點

利用上面的查找函數searchPos()找到要插入的前一個位置

int insertLinklist(linklist H, int pos, datatype x)
{
	//1.找到插入位置的前一項
	linklist p;
	if(0 == pos)
		p = H;
	else
		p = search(H, pos-1);

	if(NULL == p)
		return -1;

	//2.申請新結點
	linklist pnew = (linklist)malloc(sizeof(linknode));
	if(NULL == pnew)
	{
		printf("insert: 申請新結點失敗\n");
		return -1;
	}

	//3.給新結點指派
	pnew->data = x;
	//“先連後斷”
	pnew->next = p->next;
	p->next = pnew;

	return 0;
}
           

删

删除結點

int deleteLinkList(linklist H, int pos)
{
	//判空
	if(NULL == H->next)
	{
		printf("連結清單為空\n");
		return -1;
	}
	
	//p儲存删除的前一個位置, q儲存要删除的位置
	linklist p = NULL, q = NULL;

	if(pos>=0 && pos<=linkLength(H))//保證位置有效
	{
		if(pos == 0)
			p = H;
		else		
			p = searchPos(H, pos-1);

		//儲存删除結點
		q = p->next;
		//删除該結點
		p->next = q->next;
		//釋放該結點
		free(q);
		q = NULL;
	}
	else
	{
		printf("deleteLinkList：the pos is error\n");
		return -1;
	}
		
	return 0;
}
           

逆序輸出

利用頭插法

void reverseLinkList(linklist H)
{
	//p儲存無頭連結清單的一個結點，q儲存要接入頭節點後面的結點
	linklist p = NULL, q = NULL;

	//1.一分為二，分為頭結點和無頭連結清單兩部分
	p = H->next;
	H->next = NULL;

	//2.依次從無頭連結清單中取第一個結點出來頭插
	while(p != NULL)
	{
		//取無頭連結清單的第一個結點
		q = p;
		p = p->next;

		q->next = H->next;
		H->next = q;
	}
}
           

排序

void orderLinkList(linklist H)
{
	linklist p = NULL;//儲存無頭連結清單的第一個結點
	linklist q = NULL;//儲存插入結點
	linklist r = NULL;//儲存要插入位置的前一個結點

	//1.一分為二，分為頭結點和無頭連結清單兩部分
	p = H->next;
	H->next = NULL;

	//2.從無頭連結清單中取第一個結點，有序插入到有頭連結清單中
	while(p != NULL)
	{
		//取無頭連結清單的第一個結點
		q = p;
		p = p->next;

		//從頭開始找插入位置的前一個結點
		r = H;
		while(r->next && (r->next->data < q->data))
			r = r->next;

		//找到了，就插入該結點
		q->next = r->next;
		r->next = q;
	}
}
           

清空

清空是将連結清單置空，頭結點保留，表仍然可以用。

銷毀不僅要将有效結點全部删除，頭結點也要删除，表不再可用。

void clear(linklist H)
{
	linklist p, q;
	p = H->next;
	while(p != NULL)
	{
		q = p;
		p = p->next;
		
		free(q);		
	}
}
           

銷毀

void destroy(linklist H)
{
	clear(H)；
	
	free(H);
	H = NULL;
}
           

測試

#include"linklist.h"

int main()
{
	//1.調用函數建立一個空連結清單
	linklist H = createLinkList();
	if(NULL == H)
	{
		printf("建立空連結清單失敗\n");
		return -1;
	}
	//2.調用頭插函數，向連結清單裡新增資料
	printf("head insert:\n");
	headInsertLinkList(H, 111);
	headInsertLinkList(H, 555);
	headInsertLinkList(H, 333);
	headInsertLinkList(H, 777);
	headInsertLinkList(H, 666);
	//3.調用列印函數，檢視連結清單
	showLinkList(H);
	
	printf("search:\n");
	linklist p = searchPos(H, 2);
	printf("pos %d = %d\n", 2, p->data);

	//4.任意位置插入資料
	insertLinklist(H, 2, 777);
	showLinkList(H);

	//5.求表長
	printf("length = %d\n", linkLength(H));

	//6.删除結點
	deleteLinkList(H, 0);
	printf("delete: ");
	showLinkList(H);
	
	//7.逆序輸出
	reverseLinkList(H);
	printf("reverse: ");
	showLinkList(H);
	
	//8.排序
	printf("order: ");
	orderLinkList(H);
	showLinkList(H);
	
    return 0;
}