線性表的定義和特點

線性結構的基本特點：除第一個元素無直接前驅，最后一個元素無直接后繼，其他元素都有一個前驅和一個后繼。

說人話就是：第一個元素不能向前訪問，最后一個元素不能向后訪問，中間的元素都可以前后訪問其他元素。

例如：26個字母表{A,B,C,D,E,F…}就是一個線性表。
雖然該線性表中數據元素各不相同，但每個元素都具有相同的特性，都屬于同一數據對象。

線性表：由有限個數據特性相同的數據元素構成的有限序列。

如果沒有數據元素，該線性表也叫空表。

線性結構的特點

1，存在唯一 一個“第一個”與“最后一個”數據元素
2，出第一個和最后一個數據元素，其余元素都有一個前驅和一個后驅
解釋一下：前驅和后繼就是邏輯關系中的上一個元素和下一個元素
我原先以為是指針之類的。

線性表

線性表的長度可以根據需要增長或減小。還擁有任意位置的插入和刪除
線性表分為順序表和鏈表

順序存儲

線性表的順序存儲就是順序表，是指**一組地址連續的存儲單元依次存儲的數據元素。**實際就是每個元素都是依次儲存在地址連續的空間（簡稱：數組）。對于順序存儲而言，邏輯上是連續的，其物理次序上也是連續的

來看一張圖增強一下理解（這是我寫順序存儲的習慣，可能會存在差異）

對于線性表的順序存儲的而言，每個數據元素都可以通過下標來快速訪問，讀取。正規來說就是隨機存取

順序表的元素類型定義

這是我對順序存儲的結構體類型的定義

#define N 8
typedef struct elem
{
	int element;//每個數據元素中的數據項
}sel;
typedef struct seq
{
	sel* arr;//動態開辟的線性表空間的首地址，通過這個指針訪問到線性表空間
	int size;//當前已經使用了的空間的個數
	int capacity;//當前的最大的數據元素容量
}sl;

這里我為了簡單一些描述，我直接使用了每個數據元素都相當于只有int 類型的數據項。

其實就是跟通訊錄一樣，每個數據元素都是一個人的全部信息的集合（應該可以這么說吧），而數據項就是每個元素中包含的一部分。

順序表的增刪查改

對于順序表來說，絕大部分可以當成數組進行操作，當然，也就是要考慮順序的容量問題，是否需要擴容的幾個動態變化問題。

初始化順序表

void initsequence(sl* a)//初始化動態順序表
{
	a->size = 0;//數組元素以0開始計算,size是最后一個元素的下標，不是元素總數量
	a->capacity = N;//N在上面已經define了
	a->arr = (sel*)malloc(sizeof(int) * N);
}

擴容順序表

void checkcapacity(sl* a)//檢查是否需要擴容
{
	if (a->size +1== a->capacity)
	{
		a->capacity *= 2; 
		a->arr =(sel*) realloc( a->arr,sizeof(int) * (a->capacity));
		if (a->arr == NULL)
		{
			printf("realloc defect");
			exit(-1);
		}
	}
}

擴容是當準備對順序表的元素進行操作時元素個數已經達到最大容量時，由于我們的size是下標，就要加一。因為我們準備擴容，所以是不會允許size>=capacity。
同時，擴容不能一次性擴太多，否則或導致空間浪費。
又不能擴太少，少了就要多次擴容，會增加消耗。
所以，自己看情況吧。嘻嘻~

尾插法增加元素

void sequpushfront(sl* a,sel* ele)//尾插法
{
	checkcapacity(&a);//檢查是否需要擴容
	*(a->arr + a->size) =ele->element;//因為我只設置了一個int類型的如果數據元素中有多個數據項向下看
	++(a->size);
}

void sequpushfront(sl* a,sel* ele)//尾插法
{
	checkcapacity(&a);//檢查是否需要擴容
	(a->arr + a->size)->n =ele->element;//假設是有多個數據項就這樣依次匹配（a->arr + a->size）已經訪問到每個元素的地址再->n訪問到相應元素的空間進行存儲。
	++(a->size);
}

尾插法沒那么復雜，檢查一下擴容，直接在后面放入元素就行。
下面我就不再舉例了，舉一反三很容易的。

頭插法

void sequpushback(sl* a, int n)//頭插法
{
	checkcapacity(&a);//檢查是否需要擴容
	int head = 0;
	int end = a->size;
	while (end>=head)
	{
		*(a->arr + end + 1) = *(a->arr + end);
		
		--end;
	}
	++(a->size);
	*(a->arr + head) = n;
}

頭插法就需要將放入位置后的元素全部向后移動一個位置。
但是，怎么移又是要考慮一下的問題。

是從前向后開始移動，還是從最后一個元素開始移動。

如果是從前向后移動

會造成這個樣子，后面元素就一直是1，則，這種方法就是錯誤的。

再來看看從后向前移動

這種方法是可以行的通的。
先擴容
再元素向后移，再頭插。

void sequpushback(sl* a, sel* ele)//頭插法
{
	checkcapacity(&a);//檢查是否需要擴容
	int head = 0;
	int end = a->size;
	while (end>=head)
	{
		*(a->arr + end + 1) = *(a->arr + end);
		
		--end;
	}
	++(a->size);
	*(a->arr + head) = ele->element;
}

任意位置刪除

刪除就不頭刪尾刪了，直接任意位置刪除。

找到那個元素的下標，再開始向前覆蓋
對于刪除而言，元素移動又是一個麻煩事。
這次我們對于刪除而言，元素得從前向后開始移動。

void sequpopmid(sl* a, int n)//中間刪除，n是要刪除的位置
{
	assert(n>=0&&n<=a->size);
	for (int i = n ; i < a->size-1; i++)
	{
		*(a->arr + i) = *(a->arr + i + 1);
	}
	--(a->size);
}

刪除后要將邊界也就是size自減，防止越界。

任意位置添加

傳要添加的位置，再開始向后移動。

void sequpushmid(sl* a, int n,sel* ele)//中間添加
{
	assert(n>=0&&n=<a->size+1);//要在有效位置添加
	checkcapacity(&a);//檢查是否需要擴容
	int head = n;
	int end = a->size;
	while (end>=head)
	{
		*(a->arr + end + 1) = *(a->arr + end);
		--end;
	}
	++(a->size);
	*(a->arr + head) = ele->element;
}

其實就是頭插法的一種變形。

小總結

對于數組刪除元素，要從前向后開始移動。
而對于數組增加元素，要從后向前開始移動。
同時刪除添加的位置都要符合條件，不能越界。

線性表的鏈式存儲

該存儲結構的存儲特點是：用一組任意的存儲單元存儲線性表的數據元素。（這組存儲單元可以是連續的也可以是不連續的，簡稱：隨機分布的存儲單元）

數據域與指針域

而每個分配到存儲單元都要分為兩個部分：數據域與指針域。
這兩個域或者信息組成數據元素的存儲映像。是邏輯層次的元素在物理層次的投影。也叫結點。

• 數據域：儲存每個數據元素，包括各個數據項
• 指針域：儲存一個指針，也就是下一個結點的地址

注意，鏈式儲存也就是鏈表，其每個結點的地址都是隨機的，并不是像順序表一樣，每個空間依次排列。

鏈表有超多種結構，如：單鏈表，單向/雙向循環鏈表，雙向鏈表，二叉鏈表，十字鏈表，鄰鏈表，鄰接多重表等。

本文主要分析單鏈表，循環鏈表，雙向鏈表。其余的暫時不分析（其實是我不會，目前比較菜），以后會補充分析。

數據結構最好先畫圖，這樣可以增強理解與分析。

大致了解一下鏈表的結構。

由于鏈表中的每個結點的物理關系是不確定的，是隨機的，就需要靠指針域來表示，構成邏輯關系。指針指向是十分重要的。

這個哨兵位的頭節點的可要可不要的。

#include "linkedlist.h"
void test()
{
	list* head;
	list* last;
	initLinkedlist(&head,&last);
	pushlast(&last, 1);//尾插法
	pushlast(&last, 2);
	pushlast(&last, 3);
	pushlast(&last, 4);
	pushfront(&head, 5);//頭插法
	pushfront(&head, 8);//頭插法
	pushfront(&head, 7);//頭插法
	pushfront(&head, 6);//頭插法
	popchoice(&head, 0);//任意位置刪除
	//poshposition(&head, 3);//任意位置插入
	printlist(&head);//打印
}
int main(void)
{
	test();
	return 0;
}

先分析哨兵位的鏈表，好理解

初始化鏈表

void initLinkedlist(list** head,list** last)//初始化鏈表
{
	*head = (list*)malloc(sizeof(list));
	(*head)->next = NULL;
	*last=*head;
}

head就是哨兵位，而這個last，是要來定位最后一個結點，當last指向head時，就代表是一個空表。
由于我是在測試函數中創建了哨兵結點和尾結點指針，所以要對指針進行操作得傳一個二級指針，傳址調用才能才能對鏈表進行影響。
當尾結點指向哨兵結點時，表示是一個空表。

尾插法增加鏈表結點

void pushlast(list** last, int num)//尾插法
{
	list* new = (list*)malloc(sizeof(list));
	new->n = num;
	new->next = (*last)->next;
	(*last)->next = new;
	(*last) = new;
}

要在尾結點，也就是last結點。

尾插結點圖解，就是這樣的。
同時，當last->next的指向newnode后，last也要再移向newnode，因為newnode變成了尾結點，下次插入會在這次newnode的后面進行插入。

頭插法添加鏈表結點

void pushfront(list** head, int num)//頭插法
{
	list* new = (list*)malloc(sizeof(list));
	new->n = num;
	new->next = (*head)->next;
	(*head)->next = new;
}

要在哨兵位后進行插入，每次插入都要滿足在哨兵位節點后進行。

而哨兵位結點是始終不變的，我們可以通過這樣的操作不斷頭插。

打印鏈表

void printlist(list** head)//打印
{
	list* p = (*head)->next;
	while (p)
	{
		printf("%d ", p->n);
		p = p->next;
	}
}

從哨兵位結點進行遍歷，依次打印。

任意位置的刪除

void popchoice(list** head, int pos)//任意位置刪除
{
	assert(pos<8&pos>=0);
	int i = 0;
	list* pre = *head;
	list* cur = (*head)->next;
	while (i < pos)
	{
		pre = cur;
		cur = cur->next;
		i++;
	}
	pre->next = cur->next;
	free(cur);
}

由于是有哨兵位的鏈表，在任意位置刪除還好，但無哨兵位的鏈表，就有一些麻煩。

雖然差不多的變化。因位要保存結點的前一個結點地址，當沒有哨兵位的時候就需要if判斷一下。其實也沒多麻煩。
任意位置插入和刪除是一樣的。

雙向鏈表

這是另一種鏈式結構。
每個結點都具有兩個指針，一個指向上一個邏輯關系結點，一個指向下一個邏輯關系結點。

這一般使用一個哨兵位的結點，可以創建使用雙向鏈表的步驟更簡單。
對于雙向鏈表與單鏈表而言，雙向鏈表在鏈表的插入，刪除以及多個操作上更具有優勢。

如：尾插。
對于單鏈表，要指針遍歷找到尾結點，再插入。時間復雜度為O(N).
而雙向鏈表，他的頭結點的prev指針指向了最后一個結點，根本不需要依次遍歷。

像一些插入操作
如：前插
單鏈表都要準備兩個指針。
而雙向鏈表直接訪問prev指針就可以找到上一個結點。

雖然，指針較多可能比單鏈表麻煩，但整體操作上，卻要簡單。

而且，在以后的很多結構上，單鏈表都不會拿出來單獨使用，而是作為某個數據結構的一部分。雙向鏈表才是會作為一個主體來使用。

測試雙向鏈表（主函數）

#include "doubly_Linkedlist.h"
void doublelinkedlist1()
{
	doulink head;
	initlinkedlist(&head);//初始化雙向鏈表
	LinkedlistFrontPush(&head, 1);//頭插法
	LinkedlistFrontPush(&head, 2);//頭插法
	LinkedlistFrontPush(&head, 3);//頭插法
	LinkedlistFrontPush(&head, 4);//頭插法
	LinkedlistFrontPush(&head, 5);//頭插法
	LinkedlistBackpush(&head, 6);//尾插法
	LinkedlistBackpush(&head, 7);//尾插法
	LinkedlistBackpush(&head, 8);//尾插法
	LinkedlistBackpush(&head, 9);//尾插法
	LinkedlistBackpush(&head, 10);//尾插法	
	LinkedlistFrontPop(&head);//頭刪
	LinkedlistFrontPop(&head);//頭刪
	LinkedlistFrontPop(&head);//頭刪
	LinkedlistBackPop(&head);//尾刪
	LinkedlistBackPop(&head);//尾刪
	LinkedlistBackPop(&head);//尾刪
	LinkedlistBackPop(&head);//尾刪
	LinkedlistBackPop(&head);//尾刪
	LinkedlistPrint(&head);//打印鏈表	
}
int main(void)
{
	doublelinkedlist1();
}

因為我是創建了一個結構體變量，要對其進行操作，需要傳址調用，如果傳值調用會，導致實際上哨兵并未改變，只是改變了函數中的形參。

初始化雙向鏈表

void initlinkedlist(doulink* head)//初始化雙向鏈表
{
	(*head).next = head;
	(*head).prev = head;
}

因為雙向鏈表要形成一個閉環，初始化時也要形成閉環

頭插法插入元素

void LinkedlistFrontPush(doulink* head, lint n)//頭插法
{
	doulink* newnode = (doulink*)malloc(sizeof(doulink));
	newnode->num = n;
	doulink*phead=(*head).next;//原頭節點 
	newnode->next = phead;//新的后驅指針接入下一個
	(*head).next = newnode;//將哨兵鏈接新結點
	newnode->prev = head;//新結點的前驅指針指向哨兵
	phead->prev = newnode;//原頭結點的前驅指針指向新的頭節點
}

尾插法插入元素

void LinkedlistBackpush(doulink* head, lint n)//尾插法
{
	doulink* newnode = (doulink*)malloc(sizeof(doulink));
	newnode->num = n;
	doulink* plast = (*head).prev;//找到尾結點
	newnode->prev = plast;//新的尾接入原尾結點
	newnode->next = plast->next;//新接入哨兵
	plast->next = newnode;//原尾結點next指向新的尾
	(*head).prev = newnode;//頭節點的prev指向新的尾結點，形成閉環
}

有鏈表中多個結點的情況

尾刪法刪除結點

void LinkedlistBackPop(doulink* head)//尾刪
{	
	doulink* last = (*head).prev;//找到要刪除的尾結點
	doulink* llast = last->prev;//找到刪除后的新的尾結點
	if (last == head)
	{
		printf("Empty List\n");
		return;
	}
	(*head).prev = llast;//改變哨兵結點prev指向
	llast->next = last->next;//讓新的尾結點的next接入哨兵
	free(last);//刪除內存
}

頭刪法刪除結點

void LinkedlistFrontPop(doulink* head)//頭刪
{
	doulink* phead = (*head).next;
	doulink* second = phead->next;
	if (phead == head)
	{
		printf("Empty List\n");
		return;
	}
	second->prev = phead->prev;
	(*head).next = second;
	free(first);
}

對于頭插尾插，尾刪頭刪，一定要注意順序，不然可能會導致指針指向錯誤的地方。

而對于雙向鏈表的刪除插入，不需要多個指針，這樣要方便很多。

以下是代碼的全部主體

doubly-Linked list.c文件

#include "doubly_Linkedlist.h"
void initlinkedlist(doulink* head)//初始化雙向鏈表
{
	(*head).next = head;
	(*head).prev = head;
}
void LinkedlistFrontPush(doulink* head, lint n)//頭插法
{
	doulink* newnode = (doulink*)malloc(sizeof(doulink));
	newnode->num = n;
	doulink*phead=(*head).next;//原頭節點 
	newnode->next = phead;//新的后驅指針接入下一個
	(*head).next = newnode;//將哨兵鏈接新結點
	newnode->prev = head;//新結點的前驅指針指向哨兵
	phead->prev = newnode;//原頭結點的前驅指針指向新的頭節點
}
void LinkedlistBackpush(doulink* head, lint n)//尾插法
{
	doulink* newnode = (doulink*)malloc(sizeof(doulink));
	newnode->num = n;
	doulink* plast = (*head).prev;//找到尾結點
	newnode->prev = plast;//新的尾接入原尾結點
	newnode->next = plast->next;//新接入哨兵
	plast->next = newnode;//原尾結點next指向新的尾
	(*head).prev = newnode;//頭節點的prev指向新的尾結點，形成閉環
}
void LinkedlistFrontPop(doulink* head)//頭刪
{
	doulink* phead = (*head).next;
	doulink* second = phead->next;
	if (phead == head)
	{
		printf("Empty List\n");
		return;
	}
	second->prev = phead->prev;
	(*head).next = second;
}
void LinkedlistBackPop(doulink* head)//尾刪
{
	doulink* last = (*head).prev;//找到要刪除的尾結點
	doulink* llast = last->prev;//找到刪除后的新的尾結點
	if (last == head)
	{
		printf("Empty List\n");
		return;
	}
	(*head).prev = llast;//改變哨兵結點prev指向
	llast->next = last->next;//讓新的尾結點的next接入哨兵
	free(last);
}
void LinkedlistPrint(doulink* head)//打印鏈表
{
	doulink* cur = (*head).next;
	while (cur != head)
	{
		printf("%d ", cur->num);
		cur = cur->next;
	}
}

doubly-Linkedlist.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int lint;
typedef struct doulinked
{
	lint num;
	lint* prev;
	lint* next;
}doulink;
void initlinkedlist(doulink* head);//初始化雙向鏈表
void LinkedlistFrontPush(doulink* head, lint n);//頭插法
void LinkedlistBackpush(doulink* head, lint n);//尾插法
void LinkedlistFrontPop(doulink* head);//頭刪
void LinkedlistBackPop(doulink* head);//尾刪
void LinkedlistPrint(doulink* head);//打印鏈表

以上就是C語言編程數據結構線性表之順序表和鏈表原理分析的詳細內容，更多關于C語言數據結構線性表順序表和鏈表的資料請關注服務器之家其它相關文章！

感謝閱讀~

原文鏈接：https://blog.csdn.net/weixin_52199109/article/details/115240381