目錄

一.線性表

二.順序表實現(xiàn)

?2.1 概念及結(jié)構(gòu)

?2.2 動態(tài)順序表

2.2.1 初始化與銷毀函數(shù)

2.2.2 打印函數(shù)

2.2.3?尾插函數(shù)

2.2.4 尾刪函數(shù)

2.2.5 擴容函數(shù)

2.2.6 頭插函數(shù)

2.2.7 頭刪函數(shù)

2.2.8 任意位置插入函數(shù)

2.2.9 查找函數(shù)

2.2.10 任意位置刪除函數(shù)?

2.2.11 修改函數(shù)

三.完整代碼

四.力扣經(jīng)典例題

3.1 移除元素

3.2 合并有序數(shù)組

五.結(jié)語

一.線性表

?二.順序表實現(xiàn)

?2.1 概念及結(jié)構(gòu)

順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。

順序表一般可以分為：

• 靜態(tài)順序表：使用定長數(shù)組存儲（不好用）。
• 動態(tài)順序表：使用動態(tài)開辟的數(shù)組存儲。

由于靜態(tài)存儲N定多了怕浪費，定少了又怕不夠，我們簡單提一嘴就好了，直接重點講解動態(tài)順序表。

?2.2 動態(tài)順序表

先創(chuàng)造一個頭文件和兩個源文件 。

?

這里為了方便修改，引入了2個typedef。

2.2.1 初始化與銷毀函數(shù)

再接一個初始化函數(shù)：

注意：這里的實參傳輸?shù)叫螀⒌倪^程是傳值調(diào)用，這樣形參只是一份實參的臨時拷貝，需要實參隨形參改變的話那就得用到傳址調(diào)用。

//SeqList.h
#pragma once
#include <stdio.h>
#include <string.h>

typedef int SLDataType;
struct SeqList
{
	SQDataType*a;
	
	int size;     //存儲有效數(shù)據(jù)個數(shù)
    int capacity; //空間大小
};
//如果想方便輸入可以這么定義：
typedef struct SeqList SL;
//這樣兩個單詞就可以用SL來替代了
void SLInit(SL* ps);
?void SLDestr(SL* ps); //動態(tài)內(nèi)存開辟時候不銷毀可能會導致內(nèi)存泄漏

//Test.c
#include "SeqList.h"
int main()
{
	SL sl;
	SLInit(&sl);

	return 0;
}

返回SeqList.c文件中定義初始化與銷毀函數(shù)。?

//SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void SLInit(SL* ps)
{
	ps->a = (SLDataType*)malloc(sizeof(SLDataType)*4);//雖然一開始可以讓空間大小和malloc都置空，但這樣不方便測試，所以先給空間。
	if (ps->a == 0)
	{
		perror("malloc failed");//驗證malloc所創(chuàng)空間是否為空
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;

}
void SLDestr(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

接下來我們開始定義各種接口并實現(xiàn)其功能

//SeqList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
struct SeqList
{
	SLDataType* a;
	int size;
	int capacity;
};
typedef struct SeqList SL;

void SLInit(SL* ps);
void SLDestr(SL* ps);
//打印函數(shù)
void SLprint(SL* ps);
//擴容函數(shù)
void SLCheckCapacity(SL* ps);
//頭插尾插，頭刪尾刪
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);

//順序表在pos位置位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDataType x);

//順序表刪除pos位置的值
void SeqListErase(SL* ps, size_t pos);
//查找函數(shù)
int SLFind(SL* ps, SLDataType x);
//修改函數(shù)
void SLModify(SL* ps, int pos, SLDataType x);

2.2.2 打印函數(shù)

//打印函數(shù)
void SLprint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

2.2.3?尾插函數(shù)

關(guān)于realloc出來的空間不用free問題：

realloc分兩種擴容(都有可能發(fā)生)，當要擴容時會分析后面是否有足夠空間來分配給你，不夠就會擴容。

第一種是原地擴容：即在原數(shù)組中再開辟多余的空間，這時候開辟過后的空間地址其實與原數(shù)組a是一致的。

第二種是異地擴容：即不在原空間，而是重新開辟出新的空間，新空間滿足了擴容需求的同時還會把原數(shù)組中的元素拷貝過來。這時候原來的空間就會銷毀。

其實我們可以測試一下relloc會是哪種擴容：

?這種地址相同的就是原地擴容了

當我們設(shè)置大一點時就變成異地擴容了

因此解答了不用free的問題，因為realloc會自動幫你拷貝和釋放。

//尾插函數(shù)
void SLPushBack(SL* ps, SLDataType x)
{
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 *(sizeof(SLDataType)));
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	ps->a[ps->size] = x;
	ps->size++;


}

接下來我們來測試一下尾插并驗證是否擴容：

//Test.c
#include <stdio.h>
#include "SeqList.h"
int main()
{
	SL sl;
	SLInit(&sl);
	/*int* p1 = (int*)malloc(12);
	int* p2 = realloc(p1, 10);
	printf("%p, %p\n", p1, p2);*/
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPushBack(&sl, 6);
	SLprint(&sl);
	SLDestr(&sl);

	return 0;
}

2.2.4 尾刪函數(shù)

當我們讓size--達到尾刪時，是否需要把該處空間free掉？

答案是不行，因為malloc規(guī)定是整體創(chuàng)造空間并整體釋放空間的，不能對整個空間中的一小處進行free，這是不被允許的。

如果尾刪函數(shù)僅僅是這樣寫肯定是會出錯的，當我們尾刪多次直至讓size減到了負數(shù)，那么后面就不能再進行插入了，因為size已經(jīng)越界回不來了。 所以我們得規(guī)定讓它不能越界。

?
void SLPopBack(SL* ps)
{
	//只要size指向不大于0，就不給繼續(xù)尾刪并且提示報錯
	assert(ps->size > 0);
	ps->size--;
}

?

2.2.5 擴容函數(shù)

為了避免每一次的接口函數(shù)都要寫上擴容標準，我們直接定義一個擴容函數(shù)來方便我們調(diào)用。

//擴容函數(shù)
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
}

2.2.6 頭插函數(shù)

基本思路是把空間里面原有的元素往后移動，記住是從最末尾的元素開始，如果從首元素開始移動，那么會覆蓋掉后一個元素。

//頭插函數(shù)
void SLPushFront(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

我們繼續(xù)來測試一下

//測試函數(shù)
void TestSeqList2()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPushBack(&sl, 6);
	SLPopBack(&sl);
	
	SLprint(&sl);

	SLPushFront(&sl, 20);
	SLPushFront(&sl, 30);
	SLPushFront(&sl, 40);
	SLprint(&sl);
	SLDestr(&sl);

}

2.2.7 頭刪函數(shù)

在頭刪函數(shù)中我們則是要做到把后一位的元素往前一位覆蓋的效果，別忘了最后再ps->size--

這段頭刪函數(shù)還是存在問題，如果size為0時，while不進入循環(huán)但size還是會--，這樣又會造成之前的越界問題。所以要記得斷言！

//頭刪函數(shù)
void SLPopFront(SL* ps)
{
	assert(ps->size > 0);
	int begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;

}

進行試驗：先尾刪3次，再頭刪一次

?2.2.8 任意位置插入函數(shù)

我們用斷言來規(guī)定只能在數(shù)組元素范圍內(nèi)插入，接著再添加擴容函數(shù)。

既然要在某個位置中插入元素，那么它后面的元素就要往后移動，這里同樣設(shè)置一個end，pos為我們想插入的下標。

//順序表在pos位置位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;


	
}

接下來進行試驗：我們先頭插6 5 4 3 2 1，再從下標為1的位置中插入20.

?

當我們完成Insert函數(shù)其實可以發(fā)現(xiàn)，它可以在頭插和尾插函數(shù)里面進行復用。效果是一樣的。

?2.2.9 查找函數(shù)

//查找函數(shù)
int SLFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}

	}
	return -1;
}

查找函數(shù)通常是跟其他接口函數(shù)搭配使用的，就比如與Insert搭配。

void TestSeqList3()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5); 
	SLprint(&sl);

	SeqListInsert(&sl, 3, 40);
	SLprint(&sl);
	int x;
	scanf("%d", &x);
	int pos = SLFind(&sl, x);
	if (pos != -1)
	{
		SeqListInsert(&sl, pos, x * 10);
	}
	SLprint(&sl);
	SLDestr(&sl);

}

2.2.10 任意位置刪除函數(shù)

老規(guī)矩，我們先斷言pos只能在ps->size的范圍內(nèi)進行刪除，當我們選定好要刪除的下標時，需要把其后面的元素依次往前覆蓋，這樣就可以用覆蓋來刪除某一位置的元素了。

//順序表刪除pos位置的值
void SeqListErase(SL* ps, size_t pos)
{
	assert(pos >= 0 && pos < ps->size);//注意范圍已經(jīng)改變
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;

}

進行試驗：在任意位置插入函數(shù)實現(xiàn)的結(jié)果后我們再刪除下標為1的元素

與Insert同理，Erase同樣是可以復用的。

?2.2.11 修改函數(shù)

這里只需要注意斷言使修改的位置在有效范圍內(nèi)就行了。

//修改函數(shù)

void SLModify(SL* ps, int pos, SLDataType x)
{
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}

?至此增刪查改結(jié)束了，我們可以編輯一個菜單來總結(jié)這些功能：

后面就慢慢用stitch語句慢慢完善就好了。?

?

三.完整代碼

//SeqList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
struct SeqList
{
	SLDataType* a;
	int size;
	int capacity;
};
typedef struct SeqList SL;

void SLInit(SL* ps);
void SLDestr(SL* ps);
//打印函數(shù)
void SLprint(SL* ps);
//擴容函數(shù)
void SLCheckCapacity(SL* ps);
//頭插尾插，頭刪尾刪
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);

//順序表在pos位置位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDataType x);

//順序表刪除pos位置的值
void SeqListErase(SL* ps, size_t pos);
//查找函數(shù)
int SLFind(SL* ps, SLDataType x);
//修改函數(shù)
void SLModify(SL* ps, int pos, SLDataType x);

//SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void SLInit(SL* ps)
{
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);//雖然一開始可以讓空間大小和malloc都置空，但這樣不方便測試，所以先給空間。
	if (ps->a == 0)
	{
		perror("malloc failed");//驗證malloc所創(chuàng)空間是否為空
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;

}
void SLDestr(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

//打印函數(shù)
void SLprint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

//擴容函數(shù)
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
}

//尾插函數(shù)
void SLPushBack(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;


}

//尾刪函數(shù)
void SLPopBack(SL* ps)
{
	//只要size指向不大于0，就不給繼續(xù)尾刪并且提示報錯
	assert(ps->size > 0);
	ps->size--;
}

//頭插函數(shù)
void SLPushFront(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}


//頭刪函數(shù)
void SLPopFront(SL* ps)
{
	assert(ps->size > 0);
	int begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;

}

//順序表在pos位置位置插入x
void SeqListInsert(SL* ps, size_t pos, SLDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;


	
}
//查找函數(shù)
int SLFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}

	}
	return -1;
}

//順序表刪除pos位置的值
void SeqListErase(SL* ps, size_t pos)
{
	assert(pos >= 0 && pos < ps->size);//注意范圍已經(jīng)改變
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;

}
//修改函數(shù)

void SLModify(SL* ps, int pos, SLDataType x)
{
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//Test.c
#include <stdio.h>
#include "SeqList.h"
void TestSeqList1()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPushBack(&sl, 6);
	SLPopBack(&sl);
	SLprint(&sl);
	SLDestr(&sl);

}
void TestSeqList2()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPushBack(&sl, 6);
	SLPopBack(&sl);
	
	SLprint(&sl);

	SLPushFront(&sl, 20);
	SLPushFront(&sl, 30);
	SLPushFront(&sl, 40);
	SLprint(&sl);
	SLDestr(&sl);

}

void TestSeqList3()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5); 
	SLprint(&sl);

	SeqListInsert(&sl, 3, 40);
	SLprint(&sl);
	int x;
	scanf("%d", &x);
	int pos = SLFind(&sl, x);
	if (pos != -1)
	{
		SeqListInsert(&sl, pos, x * 10);
	}
	SLprint(&sl);
	SLDestr(&sl);

}


int main()
{
	/*SL sl;*/
	/*SLInit(&sl);*/
	/*int* p1 = (int*)malloc(12);
	int* p2 = realloc(p1, 10);
	printf("%p, %p\n", p1, p2);*/
	//TestSeqList1();
	//TestSeqList2();
	TestSeqList3();

	return 0;
}

四.力扣經(jīng)典例題

3.1 移除元素

鏈接：力扣——移除元素

?

?一般我們的思路就是2.2.10任意位置刪除元素的思想：

挨個遍歷，如果指向的下標元素與val相同，那么把后面的元素依次覆蓋，依次反復做到刪除

?假設(shè)第一次排列移動了n次，那么第2次刪除排列就是n-1次，等差數(shù)列求和一共執(zhí)行了n^2次

?

?新數(shù)組拷貝回去后因為是malloc出來的，所以再把它釋放掉就行了。空間復雜度為O（N）

這個想法核心是兩個指針：一開始先讓它們指向同一位置，用src來識別該值是否是val，如果不是就把這個值傳到dst那里去，在同等指向時好像沒什么不同，因為dst確實與src指向同一方向，然后二者共同向下一位進發(fā)。

轉(zhuǎn)折點就是當src指向了第一個2（val的值）時，dst雖然也指向了2，但是dst不動，src向下一位進發(fā)，又指向了第二個2，dst還是不動，src繼續(xù)進發(fā)指向了3.

最精彩的地方，因為src指向的3不是val（2）,所以src會把3傳給dst，那么dst原本指向的第一個2就會被改變成3，以此類推我們會發(fā)現(xiàn)當src走完時，dst已經(jīng)把2都給覆蓋了。

?

另外我們也不用擔心在str出去后原數(shù)組還有val要怎么辦，因為問題是要求返回新數(shù)組的長度，所以dst的指向本身就可以代表新數(shù)組長度，所以不用管dst后面的元素。

int removeElement(int* nums, int numsSize, int val)
{
	int n = numsSize;
	int src = 0;
	int dst = 0;
	while (src < n)
	{
		if (nums[src] != val)
		{
			nums[dst] = nums[src];
			src++;
			dst++;
			
		}
		else if (nums[src] == val)
		{
			src++;
		}
	}
	return dst;
}

3.2 合并有序數(shù)組

鏈接：力扣——合并有序數(shù)組

?

這一道題也可以通過使用雙指針的方法來進行合并有序數(shù)組：

首先，我們讓兩個指針都分別指向數(shù)組末尾的有效元素，然后同時進行比較。一開始a指向3，b指向6，6比3大，那么把b指向的6放入c中，同時b指向前一位的5，c也指向前一位的0.

a因為3比6小，所以還是指向a。

接著我們開始第二輪比較，指向3的a與指向5的b中，b更大所以重復操作b--,c在接受b傳送的5后也跟著向前一位，c--。

現(xiàn)在a仍指向3，而b已經(jīng)指向2了，3比2大，所以換成a把3傳給c，然后二者都向前一位--。

至此，a向前一位指向2，b也指向2，而c指向的數(shù)值是3，讓其中一位傳給c即可，把3變成2，剩下的就不用處理了。

不過有一個問題：

當有負數(shù)的情況出現(xiàn)時，我們重復上述操作會發(fā)現(xiàn)nums1a的指向已經(jīng)移出下標了沒辦法再排序了，而-2和-5卻還沒有排進去。

所以就需要當nums1數(shù)組已經(jīng)結(jié)束時再添加一個條件，讓沒結(jié)束的nums2繼續(xù)拷貝。

void merge(int* nums1, int sums1Size, int m, int* nums2, int sum2Size, int n)
{
	int end1 = m - 1;//第一個數(shù)組有效元素尾部
	int end2 = n - 1;//第二個數(shù)組有效元素尾部
	int end = m + n - 1;//第一個數(shù)組尾部
	while (end1 >= 0 && end2 >= 0)
	{
		if (nums1[end1] > nums2[end2])
		{
			nums1[end] = nums1[end1];
			end1--;
			end--;
		}
		else
		{
			nums1[end] = nums2[end2];
			end2--;
			end--;
		}
	}
	while (end2 >= 0)
	{
		nums1[end] = nums2[end2];
		end2--;
		end--;
	}
}

五.結(jié)語

我們可以發(fā)現(xiàn)做上述兩道題和分析順序表的時候最重要的思想就是學會畫圖，只要畫圖邏輯夠清晰，那么代碼是很容易寫出來滴~文章來源地址http://www.zghlxwxcb.cn/news/detail-722610.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——線性表之順序表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！