線性表（List）：零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列。

在較復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。在這種情況下，常把數(shù)據(jù)元素稱為記錄，含有大量記錄的線性表又稱為文件

順序表

1、順序表的基本概念

概念：用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，這種存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表。

特點(diǎn)：邏輯上相鄰的數(shù)據(jù)元素，物理次序也是相鄰的。

鏈表

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-NpMMu49F-1678256000198)(C:\Users\Lenovo\AppData\Roaming\Typora\typora-user-images\image-20230301091717476.png)]

1 簡(jiǎn)介

鏈表概念

• 鏈表是一種隨機(jī)存儲(chǔ)在內(nèi)存中的節(jié)點(diǎn)對(duì)象集合。
• 節(jié)點(diǎn)包含兩個(gè)字段，即存儲(chǔ)在該地址的數(shù)據(jù)和包含下一個(gè)節(jié)點(diǎn)地址的指針。
• 鏈表的最后一個(gè)節(jié)點(diǎn)包含指向null的指針。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-VhHZYb70-1678256000199)(image/2021-03-12-21-00-33.png)]

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-SclxGWqi-1678256000199)(image/2021-03-12-21-01-53.png)]

鏈表特點(diǎn)

• 鏈表不需要連續(xù)存在于存儲(chǔ)器中。節(jié)點(diǎn)可以是存儲(chǔ)器中的任何位置并鏈接在一起以形成鏈表。這實(shí)現(xiàn)了空間的優(yōu)化利用。
• 鏈表大小僅限于內(nèi)存大小，不需要提前聲明。
• 空節(jié)點(diǎn)不能出現(xiàn)在鏈表中。
• 在單鏈表中存儲(chǔ)基元類型或?qū)ο蟮闹怠?/li>

鏈表與數(shù)組的對(duì)比

• 數(shù)組有以下限制：

  • 在程序中使用數(shù)組之前，必須事先知道數(shù)組的大小。
  • 增加數(shù)組的大小是一個(gè)耗時(shí)的過(guò)程。在運(yùn)行時(shí)幾乎不可能擴(kuò)展數(shù)組的大小。
  • 數(shù)組中的所有元素都需要連續(xù)存儲(chǔ)在內(nèi)存中。在數(shù)組中插入任何元素都需要移動(dòng)元素之前所有的數(shù)據(jù)。

• 鏈表是可以克服數(shù)組所有限制的數(shù)據(jù)結(jié)構(gòu)。 鏈表是非常有用的，因?yàn)?#xff0c;

  • 它動(dòng)態(tài)分配內(nèi)存。鏈表的所有節(jié)點(diǎn)都是非連續(xù)存儲(chǔ)在存儲(chǔ)器中，并使用指針鏈接在一起。
  • 大小調(diào)整不再是問(wèn)題，因?yàn)椴恍枰诼暶鲿r(shí)定義大小。鏈表根據(jù)程序的需求增長(zhǎng)，并且僅限于可用的內(nèi)存空間。

2 鏈表的類型

分類

• 單鏈表
• 雙鏈表
• 循環(huán)單鏈表
• 循環(huán)雙鏈表

鏈表

鏈?zhǔn)酱鎯?chǔ)設(shè)計(jì)時(shí)，各個(gè)不同結(jié)點(diǎn)的存儲(chǔ)空間可以不連續(xù)，但是結(jié)點(diǎn)內(nèi)的存儲(chǔ)單元地址則必須連續(xù)。

typedef struct LNode {int value; // value中存放結(jié)點(diǎn)值域，默認(rèn)是int型struct Lnode *next;//指向后繼結(jié)點(diǎn)的指針
}LNode; // 定義單鏈表結(jié)點(diǎn)類型
1234

上述定義了一個(gè)結(jié)構(gòu)體，包括兩部分，一是值域，二是指針域；每當(dāng)定義一個(gè)結(jié)點(diǎn)都會(huì)產(chǎn)生這兩個(gè)區(qū)域。
這個(gè)value與next域必須是挨著的，稱這個(gè)結(jié)點(diǎn)為內(nèi)部。

假如我們定義若干個(gè)不同的結(jié)點(diǎn)，把它們連接起來(lái)成為一個(gè)單鏈表。

value區(qū)域，箭頭區(qū)域則是指針域指向邏輯上相鏈接的下一個(gè)結(jié)點(diǎn)，但是它們?cè)诳臻g上不一定連續(xù)。
而對(duì)于它們的結(jié)點(diǎn)內(nèi)部一定是連續(xù)的。若第一個(gè)結(jié)點(diǎn)占用兩個(gè)地址，那么value域的起始地址是1，則指針域的地址就是2。同理若第二個(gè)結(jié)點(diǎn)的value地址是10，則next域就是11。

因此，在進(jìn)行鏈?zhǔn)酱鎯?chǔ)設(shè)計(jì)時(shí)，各個(gè)不同結(jié)點(diǎn)完全可以存儲(chǔ)在不連續(xù)的空間上，而對(duì)于同一個(gè)結(jié)點(diǎn)內(nèi)部，不論劃分多少個(gè)區(qū)域，兩個(gè)也好，三個(gè)也罷，總之內(nèi)部的單元存儲(chǔ)地址是連續(xù)的

循環(huán)單向鏈表

1 簡(jiǎn)介

概念

• 在循環(huán)單鏈表中，鏈表的最后一個(gè)節(jié)點(diǎn)包含指向鏈表的第一個(gè)節(jié)點(diǎn)的指針。可以有循環(huán)單向鏈表以及循環(huán)雙鏈表。
• 遍歷一個(gè)循環(huán)單鏈表，直到到達(dá)開(kāi)始的同一個(gè)節(jié)點(diǎn)。循環(huán)單鏈表類似于鏈表，但它沒(méi)有開(kāi)始也沒(méi)有結(jié)束。任何節(jié)點(diǎn)的下一部分都不存在NULL值。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-4jLx1utk-1678256055499)(image/循環(huán)單向鏈表.png)]

2 數(shù)據(jù)存儲(chǔ)和實(shí)現(xiàn)

數(shù)據(jù)存儲(chǔ)

鏈表的最后一個(gè)節(jié)點(diǎn)包含鏈表的第一個(gè)節(jié)點(diǎn)的地址。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-sgXy3iXl-1678256055501)(image/2021-03-12-21-21-07.png)]

數(shù)據(jù)實(shí)現(xiàn)

• 鏈表通過(guò)結(jié)構(gòu)體和指針實(shí)現(xiàn)

struct node   
{  int data;   struct node *next;  
};  
struct node *head, *ptr;   
ptr = (struct node *)malloc(sizeof(struct node *));

• C++ STL提供了鏈表的實(shí)現(xiàn)

#include<list>list<int> li;
forward_list<int> li;

3 操作

基本操作

• 創(chuàng)建
• 遍歷、搜索
• 插入
• 刪除

實(shí)現(xiàn)

#include<stdio.h>  
#include<stdlib.h>  
struct node
{int data;struct node *next;
};
struct node *head;void beginsert();
void lastinsert();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
int main()
{int choice = 0;while (choice != 7){printf("*********Main Menu*********\n");printf("Choose one option from the following list ...\n");printf("===============================================\n");printf("1.Insert in begining\n2.Insert at last\n");printf("3.Delete from Beginning\n4.Delete from last\n");printf("5.Search for an element\n6.Show\n7.Exit\n");printf("Enter your choice?\n");scanf("%d", &choice);switch (choice){case 1:beginsert();break;case 2:lastinsert();break;case 3:begin_delete();break;case 4:last_delete();break;case 5:search();break;case 6:display();break;case 7:exit(0);break;default:printf("Please enter valid choice..");}}
}
void beginsert()
{struct node *ptr, *temp;int item;ptr = (struct node *)malloc(sizeof(struct node));if (ptr == NULL){printf("OVERFLOW");}else{printf("Enter the node data?");scanf("%d", &item);ptr->data = item;if (head == NULL){head = ptr;ptr->next = head;}else{temp = head;while (temp->next != head)temp = temp->next;ptr->next = head;temp->next = ptr;head = ptr;}printf("node inserted\n");}}
void lastinsert()
{struct node *ptr, *temp;int item;ptr = (struct node *)malloc(sizeof(struct node));if (ptr == NULL){printf("OVERFLOW\n");}else{printf("Enter Data?");scanf("%d", &item);ptr->data = item;if (head == NULL){head = ptr;ptr->next = head;}else{temp = head;while (temp->next != head){temp = temp->next;}temp->next = ptr;ptr->next = head;}printf("node inserted\n");}}void begin_delete()
{struct node *ptr;if (head == NULL){printf("UNDERFLOW");}else if (head->next == head){head = NULL;free(head);printf("node deleted\n");}else{ptr = head;while (ptr->next != head)ptr = ptr->next;ptr->next = head->next;free(head);head = ptr->next;printf("node deleted\n");}
}
void last_delete()
{struct node *ptr, *preptr;if (head == NULL){printf("UNDERFLOW");}else if (head->next == head){head = NULL;free(head);printf("node deleted\n");}else{ptr = head;while (ptr->next != head){preptr = ptr;ptr = ptr->next;}preptr->next = ptr->next;free(ptr);printf("node deleted\n");}
}void search()
{struct node *ptr;int item, i = 0, flag = 1;ptr = head;if (ptr == NULL){printf("Empty List\n");}else{printf("Enter item which you want to search?\n");scanf("%d", &item);if (head->data == item){printf("item found at location %d", i + 1);flag = 0;}else{while (ptr->next != head){if (ptr->data == item){printf("item found at location %d ", i + 1);flag = 0;break;}else{flag = 1;}i++;ptr = ptr->next;}}if (flag != 0){printf("Item not found\n");}}}void display()
{struct node *ptr;ptr = head;if (head == NULL){printf("nothing to print");}else{printf("printing values ... \n");while (ptr->next != head){printf("%d\n", ptr->data);ptr = ptr->next;}printf("%d\n", ptr->data);}}