?線性表：
順序表
概念及結(jié)構(gòu)
靜態(tài)順序表：使用定長數(shù)組存儲元素。
?動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲。
?如果將一開始動態(tài)開辟的內(nèi)存填滿，則會進行擴容，
擴容分兩種情況：
原地擴容：在已開辟的動態(tài)內(nèi)存后進行判斷，如果后方內(nèi)存大小足夠擴容到新定義的大小，則在之前開辟的內(nèi)存后面加上一段，以達到新定義內(nèi)存大??；
異地擴容：如果在已開辟的動態(tài)內(nèi)存后進行判斷，后方的大小不足以擴容到新定義的大小，則會在內(nèi)存中尋找一塊新的足夠容納新定義大小的空間，并將之前的數(shù)據(jù)拷貝到新空間，再釋放之前定義的動態(tài)內(nèi)存空間；
接口實現(xiàn)
typedef int SLDateType;
typedef struct SeqList
{
?? ?SLDateType* a;//動態(tài)開辟的數(shù)組
?? ?int size; ? ?//數(shù)據(jù)個數(shù)
?? ?int capacity;//容量空間大小
}SL;
//初始化
void SLInit(SL* ps);//釋放或銷毀
void SLDestroy(SL* ps);//顯示或打印
void SLPrintf(SL* ps);//尾插
void SLPushBack(SL* ps, SLDateType x);
//尾刪
void SLPopBack(SL* ps);
//頭插
void SLPushFront(SL* ps, SLDateType x);
//頭刪
void SLPopFront(SL* ps);//擴容
void SLCheckDestroy(SL* ps);//順序表查找
int SLFind(SL* ps,int n);// 順序表在pos位置插入x
void SLInsert(SL* ps, int pos, SLDateType x);// 順序表刪除pos位置的值
void SLErase(SL* ps, int pos);//順序表修改
void SLModify(SL* ps,int pos,SLDateType x);
#define _CRT_SECURE_NO_WARNINGS 1
#include "Sequence.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//初始化
void SLInit(SL* ps)
{
?? ?ps->a = (SLDateType*)malloc(sizeof(SLDateType*)*4);
?? ?if (ps->a == NULL)
?? ?{
?? ??? ?perror("malloc failed");
?? ??? ?exit(-1);
?? ?}
?? ?ps->size = 0;
?? ?ps->capacity = 4;
}
//釋放或銷毀
void SLDestroy(SL* ps)
{
?? ?free(ps->a);
?? ?ps->a = NULL;
?? ?ps->capacity = ps->size = 0;
}
//顯示或打印
void SLPrintf(SL* ps)
{
?? ?int i = 0;
?? ?for (i = 0; i < ps->size; i++)
?? ?{
?? ??? ?printf("%d ", ps->a[i]);
?? ?}
?? ?printf("\n");
}//擴容
void SLCheckDestroy(SL* ps)
{
?? ?if (ps->size == ps->capacity)
?? ?{
?? ??? ?SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * 2 * ps->capacity);
?? ??? ?if (tmp == NULL)
?? ??? ?{
?? ??? ??? ?perror("realloc failed");
?? ??? ??? ?exit(-1);
?? ??? ?}
?? ??? ?ps->a = tmp;
?? ??? ?ps->capacity *= 2;
?? ?}
}
//尾插void SLPushBack(SL* ps, SLDateType x)
{
?? ?SLCheckDestroy(ps);?? ?//ps->a[ps->size] = x;
?? ?//ps->size++;?? ?SLInsert(ps,ps->size,x);
}//尾刪
void SLPopBack(SL* ps)
{
?? ?assert(ps);
?? ?//溫柔型
?? ?//if (ps->size == 0)
?? ?//{
?? ?//?? ?return;
?? ?//}
?? ?
?? ?//暴力型
?? ?//assert(ps->size > 0);?? ?//ps->size--;
?? ?SLErase(ps, ps->size - 1);
}
//頭插void SLPushFront(SL* ps, SLDateType x)
{
?? ?assert(ps);
?? ?SLCheckDestroy(ps);
?? ?//int i = 0;
?? ?//for (i = 0; i < ps->size ; i++)
?? ?//{
?? ?//?? ?ps->a[ps->size-i] = ps->a[ps->size - i -1];
?? ?//}
?? ?//ps->a[0] = x;
?? ?//ps->size++;
?? ?SLInsert(ps, 0, x);
}//頭刪
void SLPopFront(SL* ps)
{
?? ?//防止越界
?? ?assert(ps->size > 0);?? ?//int i = 0;
?? ?//for (i = 0; i < ps->size - 1; i++)
?? ?//{
?? ?//?? ?ps->a[i] = ps->a[i+1];
?? ?//}
?? ?//ps->size--;?? ?SLErase(ps, 0);
}//查找
int SLFind(SL* ps, int n)
{
?? ?int i = 0;
?? ?for (i = 0; i < ps->size; i++)
?? ?{
?? ??? ?if (ps->a[i] == n)
?? ??? ?{
?? ??? ??? ?return i;
?? ??? ?}
?? ?}
?? ?return -1;
}
// 順序表在pos位置插入xvoid SLInsert(SL* ps, int pos, SLDateType x)
{
?? ?assert(ps);
?? ?//=0相當于頭插，=size等于尾插
?? ?assert(pos >= 0 && pos <= ps->size);?? ?SLCheckDestroy(ps);
?? ?int start = ps->size - 1 ;
?? ?while (start >= pos)
?? ?{
?? ??? ?ps->a[start + 1] = ps->a[start];
?? ??? ?start--;
?? ?}
?? ?ps->a[pos] = x;
?? ?ps->size++;
}
// 順序表刪除pos位置的值void SLErase(SL* ps, int pos)
{
?? ?assert(ps);?? ?assert(pos >= 0 && pos < ps->size);
?? ?int begin = pos + 1;
?? ?while (begin < ps->size)
?? ?{
?? ??? ?ps->a[begin - 1] = ps->a[begin];
?? ??? ?begin++;
?? ?}
?? ?ps->size--;
}//順序表修改
void SLModify(SL* ps, int pos, SLDateType x)
{
?? ?assert(ps);
?? ?assert(pos >= 0 && pos < ps->size);?? ?ps->a[pos];
}
?值得注意的是：
如果沒有使用溫柔型或者暴力型判斷，可能會發(fā)生數(shù)組越界，但是一般情況下，編譯器不會報錯，因為編譯器只在數(shù)組兩天的特定位置放置了越界標記，需要觸發(fā)才會報錯，觸發(fā)一般是在編譯結(jié)束時到數(shù)組越界標記訪問，此時越界了，但沒有在此處賦值，也不會報錯。
順序表總結(jié)：
缺點：
1.頭部和中部插入和刪除效率不高O(n);
2.空間不足時，擴容有一定的消耗（尤其是異地擴容）如：開辟空間，拷貝，釋放舊空間；
3.擴容邏輯，可能存在空間浪費（200個，但是只用110個）。
優(yōu)點：
1.尾插尾刪足夠快；
2.下標的隨機訪問和修改。
鏈表
鏈表的概念及結(jié)構(gòu):
特點：按需申請釋放
邏輯上分析鏈表如圖：
?值得注意：
1.上圖，鏈式結(jié)構(gòu)在邏輯上是連續(xù)的，在物理上不一定是連續(xù)的；
2.現(xiàn)實中的結(jié)點一般是在堆上申請；
3.堆上申請的空間，可能連續(xù)，也可能不連續(xù)。?
物理上分析鏈表如下：?
1.單向鏈表的實現(xiàn)：
// 1 、無頭 + 單向 + 非循環(huán)鏈表增刪查改實現(xiàn)typedef int SLTDateType ;typedef struct SListNode{SLTDateType data ;struct SListNode * next ;} SListNode ;// 動態(tài)申請一個結(jié)點SListNode * BuySListNode ( SLTDateType x );// 單鏈表打印void SListPrint ( SListNode * plist );// 單鏈表尾插void SListPushBack ( SListNode ** pplist , SLTDateType x );// 單鏈表的頭插void SListPushFront ( SListNode ** pplist , SLTDateType x );// 單鏈表的尾刪void SListPopBack ( SListNode ** pplist );// 單鏈表頭刪void SListPopFront ( SListNode ** pplist );// 單鏈表查找SListNode * SListFind ( SListNode * plist , SLTDateType x );// 單鏈表在 pos 位置之后插入 x// 分析思考為什么不在 pos位置之前插入？void SListInsertAfter ( SListNode * pos , SLTDateType x );// 單鏈表刪除 pos 位置之后的值// 分析思考為什么不刪除 pos 位置？void SListEraseAfter ( SListNode * pos );//銷毀
void SListDestory ( SListNode** phead );
?// 動態(tài)申請一個結(jié)點
SListNode* BuySListNode(SLDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}?// 單鏈表打印
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}?特別需要注意的是
?
?
上面兩張圖中，圖一說明改變成員，要用成員的指針，
圖二說明改變成員的指針，要用成員的指針的指針（二級指針）?
// 單鏈表尾插
void SListPushBack(SListNode** phead, SLDataType x)
{
assert(phead);
SListNode* newnode = BuySListNode(x);
if (*phead == NULL)
{
// 改變的結(jié)構(gòu)體的指針，所以要用二級指針
*phead = newnode;
}
else
{
SListNode* tail = *phead;
while (tail->next != NULL)
{
tail = tail->next;
}
// 改變的結(jié)構(gòu)體，用結(jié)構(gòu)體的指針即可
tail->next = newnode;
}
}
// 單鏈表的頭插
void SListPushFront(SListNode** phead, SLDataType x)
{
assert(phead);
SListNode* newnode = BuySListNode(x);
newnode->next = *phead;
*phead = newnode;
}// 單鏈表的尾刪
void SListPopBack(SListNode** phead)
{
assert(phead);
//0個
assert(*phead);
//1個或以上
if ((*phead)->next == NULL)
{
free(*phead);
*phead = NULL;
}
else
{
SListNode* tail = *phead;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}// 單鏈表頭刪
void SListPopFront(SListNode** phead)
{
assert(phead);
assert(*phead);
SListNode* newnode = (*phead)->next;
free(*phead);
*phead = newnode;
}//查找
SListNode* SListFind(SListNode* phead, SLDataType x)
{
SListNode* newnode = phead;
while (newnode)
{
if (newnode->data == x)
{
return newnode;
}
newnode = newnode->next;
}
return NULL;
}//在pos之后插入x?
void SListInsertAfter(SListNode* pos, SLDataType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}//在pos之前插x
void SLTInsert(SListNode** phead, SListNode* pos, SLDataType x)
{
assert(pos);
//方法一
if (pos == *phead)
{
SListPushFront(phead, x);
}
else
{
SListNode* tail = *phead;
while (tail->next != pos)
{
tail = tail->next;
}
SListNode* newnode = BuySListNode(x);
tail->next = newnode;
newnode->next = pos;
}
//方法二
//SListNode* tail = *phead;
//while (newnode->next == NULL)
//{
// if (*phead == pos)
// {
// newnode->next = tail;
// *phead = newnode;
// }
// if (tail->next == pos)
// {
// newnode->next = tail->next;
// tail->next = newnode;
// }
// else
// {
// tail = tail->next;
// }
//}
}
// 刪除pos位置
void SLTErase(SListNode** phead, SListNode* pos)
{
assert(phead);
assert(pos);
SListNode* tail = *phead;
if (*phead == pos)
{
SListPopFront(phead);
//*phead = pos->next;
//return;
}
while (tail->next != pos->next)
{
if (tail->next == pos)
{
tail->next = tail->next->next;
}
else
{
tail = tail->next;
}
}
free(pos);
//pos = NULL;//形參不改變實參，在調(diào)用外面置空
}// 刪除pos的后一個位置
void SLTEraseAfter(SListNode* pos)
{
assert(pos);
assert(pos->next);//如果pos沒有下一個，報錯
SListNode* postNext = pos->next;
pos->next = pos->next->next;
free(postNext);
postNext = NULL;
}//銷毀?
void SListDestory(SListNode** phead)
{
assert(phead);
SListNode* cur = *phead;
while (cur)
{
SListNode* node = cur->next;
free(cur);
cur = node;
}
*phead = NULL;
}?替換發(fā)刪除：
將下一個節(jié)點的值給pos，然后刪除pos->next的節(jié)點。
2.雙向鏈表的實現(xiàn)：
// 2 、帶頭 + 雙向 + 循環(huán)鏈表增刪查改實現(xiàn)typedef int LTDataType ;typedef struct ListNode{LTDataType _data ;struct ListNode * next ;struct ListNode * prev ;} ListNode ;// 創(chuàng)建返回鏈表的頭結(jié)點 .ListNode * ListCreate ();// 雙向鏈表銷毀void ListDestory ( ListNode * plist );// 雙向鏈表打印void ListPrint ( ListNode * plist );// 雙向鏈表尾插void ListPushBack ( ListNode * plist , LTDataType x );// 雙向鏈表尾刪void ListPopBack ( ListNode * plist );// 雙向鏈表頭插void ListPushFront ( ListNode * plist , LTDataType x );// 雙向鏈表頭刪void ListPopFront ( ListNode * plist );// 雙向鏈表查找ListNode * ListFind ( ListNode * plist , LTDataType x );// 雙向鏈表在 pos 的前面進行插入void ListInsert ( ListNode * pos , LTDataType x );// 雙向鏈表刪除 pos 位置的結(jié)點void ListErase ( ListNode * pos );
?// 創(chuàng)建返回鏈表的頭結(jié)點
ListNode* BuyLTNode(LTDataType x)
{
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->data = x;
node->next = NULL;
node->prev = NULL;
return node;
}
// 創(chuàng)建返回鏈表的頭結(jié)點.
ListNode* ListCreate()
{
ListNode* head = BuyLTNode(0);
head->next = head;
head->prev = head;
return head;
}// 雙向鏈表打印
// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* node = pHead->next;
while (node != pHead)
{
printf("%d->",node->data);
node = node->next;
}
printf("NULL\n");
}// 雙向鏈表在pos的前面進行插入
// 雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newnode = BuyLTNode(x);
ListNode* oldnode = pos->prev;
newnode->prev = oldnode;
oldnode->next = newnode;
newnode->next = pos;
pos->prev = newnode;
}// 雙向鏈表刪除pos位置的節(jié)點
// 雙向鏈表刪除pos位置的節(jié)點
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* oldnode = pos->prev;
oldnode->next = pos->next;
pos->next->prev = oldnode;
free(pos);
}// 雙向鏈表尾插
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListInsert(pHead,x);
}// 雙向鏈表頭插
// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListInsert(pHead->next,x);
}// 雙向鏈表尾刪
// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{
assert(pHead);
//
assert(pHead->next != pHead);
ListErase(pHead->prev);
}
// 雙向鏈表頭刪
// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{
assert(pHead);
//
assert(pHead->next != pHead);
ListErase(pHead->next);
}// 雙向鏈表查找
// 雙向鏈表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* node = pHead->next;
while(node != pHead)
{
if (node->data == x)
{
return node;
}
node = node->next;
}
return NULL;
}// 雙向鏈表銷毀
// 雙向鏈表銷毀
void ListDestory(ListNode* pHead)
{
assert(pHead);
ListNode* oldnode = pHead->next;
while (oldnode != pHead)
{
ListNode* oldnode1 = oldnode->next;
free(oldnode);
oldnode = oldnode1;
}
free(pHead);
printf("銷毀完成！\n");
}鏈表和順序表的區(qū)別：?
緩存利用率：
文章來源：http://www.zghlxwxcb.cn/news/detail-647158.html
?以上就是個人學習線性表的個人見解和學習的解析，歡迎各位大佬在評論區(qū)探討！
感謝大佬們的一鍵三連！?感謝大佬們的一鍵三連！?感謝大佬們的一鍵三連！?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
文章來源地址http://www.zghlxwxcb.cn/news/detail-647158.html
到了這里，關于數(shù)據(jù)結(jié)構(gòu)順序表和鏈表（超詳細）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
