文章目录

• • 线性表
  • • 顺序表
    • • 顺序表的定义及结构
      • • 顺序表结构体定义
      • 动态顺序表的接口实现
      • • 顺序表尾插尾删
        • 顺序表头插头删
        • 任意位置插入删除
        • 其他基本接口
      • 数组面试题
      • • Example 1 移除元素
        • • 思路 1
          • 思路 2
          • 思路 3
        • Example 2 数组去重
        • Example 3 合并数组
        • • 思路 1
          • 思路 2
      • 顺序表的缺陷
    • 链表
    • • 链表的定义及结构
      • • 单链表结构体的定义
      • 单链表的接口实现
      • • 单链表尾插头插
        • 单链表尾删头删
        • 任意位置插入删除
        • 其他基本接口
      • 链表的分类
      • 链表面试题
      • • Example 1 移除结点
        • Example 2 反转链表
        • Example 3 中间结点
        • Example 4 输出结点

@H_22_126@

线性表

线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在现实中应用广泛的数据结构，常见的线性表有顺序表，链表，栈，队列，字符串等。

线性表在逻辑上是线性结构，可以想象成一条直线。但在物理上不一定是连续的，线性表的物理存储通常以数组和链式结果的形式存储。如图F1a;

顺序表

顺序表的定义及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，即数组的形式存储。顺序表必须从头向后依次存储，在数组上完成数据的增删查改的操作，当然顺序表一般分为动态顺序表和静态顺序表。

顺序表结构体定义

//1. 静态顺序表
#@H_406_155@define NUM 1000//元素容量
tyPEdef int SLDataType;//顺序表元素类型
typedef struct SeqList {
	SLDataType data[NUM];//顺序表数组
	int size;//元素个数
}SL;//顺序表结构体名

//2. 动态顺序表
typedef int SLDataType;
typedef struct SeqList {
	SLDataType* data;//元素数组
	int size;
	int capacITy;
}SL;

1. 结构体的用途就是描述一个复杂对象。存放数据的数组和记录元素个数和容量的变量都是为了描述顺序表这一个整体对象的不可缺少的成员变量，所以将其都放在一个名为顺序表的结构体中。
2. 静态顺序表定义相对简单，但元素容量固定，变量size用于记录有效数组元素个数。动态顺序表使用动态开辟数组，故增加一个变量capacity用于记录数组容量。
3. 使用#define定义元素容量，对结构体类型和元素类型的重命名，同样也是方便后期更改，达到“一改俱改”的效果。

动态顺序表的接口实现

静态顺序表是定长数组，只适用于数据存量确定的场景。而动顺序表是动态开辟的数组，可以灵活的增容，所以现实中基本上都是用动态顺序表。下列是基本的增删查改操作的接口函数。

//顺序表初始化
void SeqListInit(SeqList* psl, size_t capacity);
//检查空间
void CheckCapacity(SeqList* psl);
//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
//顺序表尾删
void SeqListPopBack(SeqList* psl);
//顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//顺序表头删
void SeqListPopFront(SeqList* psl);
//顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
//顺序表任意位置插入
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
//顺序表任意位置删除
void SeqListErase(SeqList* psl, size_t pos);
//顺序表销毁
void SeqListDestory(SeqList* psl);
//顺序表打印
void SeqListPRint(SeqList* psl);

顺序表尾插尾删

尾插有三种情况：顺序表没有空间或空间已满需扩容，空间未满直接插入。

尾删也要考虑到有效元素个数为0的情况。

void SeqListPushBack(SL* ps, SLDataType x) {
	CheckCapacity(ps);
	ps->data[ps->size] = x;
	ps->size++;
}
void SeqListPopBack(SL* ps) {
	assert(ps->size > 0)
	ps->size--;
}

考虑到特殊情况后，尾插尾删就很简单了。

顺序表头插头删

void SeqListPushFront(SL* ps, SLDataType x) {
	CheckCapacity(ps);
	int end = ps->size - 1;
    //移动数据
	while (end >= 0) {
		ps->data[end + 1] = ps->data[end];
		end--;
	}
    //插入
	ps->data[0] = x;
	ps->size++;
}
void SeqListPopFront(SL* ps) {
	assert(ps->size > 0);
	int begin = 1;
    //移动数据并覆盖
	while (begin < ps->size) {
		ps->data[begin - 1] = ps->data[begin];
		begin++;
	}
	ps->size--;
}

头插首先将整体也就是下标从0到size-1的元素后移一个位置。为防止内容覆盖，则必须从后向前移，方法是定义“尾指针”，每次减一从后向前遍历，最后增加一个元素即可。

头删则是将下标为1到size-1的元素前移一个位置，定义“头指针”指向第二个元素从前向后遍历，正好将第一个元素覆盖。

任意位置插入删除

void SeqListInsert(SL* ps, int pos, SLDataType x) {
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos) {
		ps->data[end + 1] = ps->data[end];
		end--;
	}
	ps->data[pos] = x;
	ps->size++;
}
void SeqListErase(SL* ps, int pos) {
	assert(pos >= 0 &amp;& pos < ps->size && ps->size > 0);
	int begin = pos + 1;
	while (begin < ps->size) {
		ps->data[begin - 1] = ps->data[begin];
		begin++;
	}
	ps->size--;
}

指定位置的插入和删除其实就是分别把头插头删的最终位置和起始位置换成指定下标pos。当然头插头删也可以用指定位置插入删除的方法实现。

其他基本接口

void SeqListInit(SL* ps) {
	ps->data = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
void SeqListDestroy(SL* ps) {
	free(ps->data);
	ps->data = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

结构体成员数组使用的是动态开辟的空间所以记得初始化和销毁内存。因为代码执行过程中越界编译器可能不会即使检测出来，销毁内存同时还有帮助检测数组越界的功能。

void CheckCapacity(SL* ps) {
	if (ps->size == ps->capacity) {
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* ptr = (SLDataType*)realloc(ps->data, newcapacity * sizeof(SLDataType));
		if (ptr == NULL) {
			perror(";malloCFail");
			exit(-1);
		}
		ps->data = ptr;
		ps->capacity = newcapacity;
	}
}

不管是尾插，头插还是任意位置插入都要考虑需扩容的情况。同样，不管是尾删，头删还是任意位置删除都要考虑有效元素个数为0的情况。故可将检测顺序表容量的代码封装成函数，以便调用。

动态开辟内存是有内存消耗的，异地扩复制内容也会增加时间消耗，所以尽量每次开辟大一点以减少开辟次数。

realloc开辟内存分为“原地扩”和“异地扩”，如果原空间后面有足够大的空间就原地扩，反之则重新开辟一段空间将原空间的内容复制过去并释放原空间返回新空间地址，称为异地扩。

int SeqListFind(SL* ps, SLDataType x) {
	for (int i = 0; i < ps->size; i++) {
		if (ps->data[i] == x) {
			return i;
		}
	}
	return -1;
}
void SeqListPrint(SL* ps) {
	for (int i = 0; i < ps->size; i++) {
		printf("%d ", ps->data[i]);
	}
	printf("n");
}

数组面试题

竞赛面试普遍采用OJ(Online Judge)的方式，OJ题型分为IO型和接口型。

1. IO型，就是输入输出函数都由被试者实现，系统进行输入输出操作，并检查程序结果是否实现。
2. 接口型，被试者仅需利用系统提供的接口写出功能函数，由系统自主调用，检查测试用例是否正确。

Example 1 移除元素

移除元素

移除数组 nums中所有数值等于 val 的元素，并返回移除后数组的新长度。

思路 1

@R_921_1304@为 O ( N 2 ) O(N^2) O(N2)，空间复杂度为 O ( 1 ) O(1) O(1)

int removeElement(int* nums, int numsSize, int val) {
    int number = numsSize;
    int* pnums = nums;
    while (pnums < nums + number) {
        if (*pnums == val) {
            int begin = pnums - nums;
            //begin是该元素的下标，numsSize-begin是该元素之后的元素个数
            while (begin < numsSize - 1) {
                nums[begin] = nums[begin + 1];
                begin++;
            }
            number--; 
        }
        else {
            pnums++;
        }
    }
    return number;
}

思路 2

时间复杂度为 O ( N ) O(N) O(N)，空间复杂度为 O ( N ) O(N) O(N)

int removeElement(int* nums, int numsSize, int val) {
    int tmp[200] = { 0 };
    int j = 0;
    //转移不是val的元素
    for (int i = 0; i < numsSize; i++) {
        if(nums[i] != val) {
            tmp[j] = nums[i];
            j++;
        }
    }
    //赋值给nums
    for(int i = 0; i < j; i++) {
        nums[i] = tmp[i];
    }
    return j;
}

思路 3

快慢指针，通过指针分别指向。可以用指针也可以用下标的方式。

时间复杂度为 O ( N ) O(N) O(N)，空间复杂度为 O ( 1 ) O(1) O(1)

int removeElement(int* nums, int numsSize, int val) {
    int* src = nums;
    int* dst = nums;
    //1. 指针版
    while (src - nums < numsSize) {
        if (*src != val) {
            *dst = *src;
            dst++;
        }
        src++;
        //是与不是，src都要++；只有赋值后dst才++
    }
    return dst - nums;
    //2. 下标版
    int src = 0, dst = 0;
    while(src < numsSize) {
        if(nums[src] != val) {
            nums[dst] = nums[src];
            dst++;
        }
        src++;
    }
    return dst;
}

Example 2 数组去重

数组去重

删除有序数组 nums 中重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。

找到一段相同数字的区间，只留一个。

int removeDuplicates(int* nums, int numsSize) {
    int begin = 0, end = 1;
    int dst = 1;
    if(numsSize == 0) {
        return 0;
    }
    while (end < numsSize) {
        if(nums[begin] == nums[end]) {
            end++;
        }
        else {
            begin = end;
            nums[dst] = nums[begin];
            end++;
            dst++;
        }
    }
    return dst;  
}

Example 3 合并数组

合并数组

两个按非递减顺序排列的整数数组nums1和nums2，合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。

思路 1

开辟新数组，将两数组的元素相比取其小值放入新数组中。

时间复杂度为 O ( M + N ) O(M+N) O(M+N)，空间复杂度为 O ( M + N ) O(M+N) O(M+N)

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int i = 0, j = 0, dst = 0;
    int nums3[200] = { 0 };   
    while (i < m && j < n) {
        if (nums1[i] <= nums2[j]) {
            nums3[dst] = nums1[i];
            dst++, i++;
        }
        else {
            nums3[dst] = nums2[j];
            dst++, j++;
        }
    }
    //剩余元素
    while (i < m) {
        nums3[dst] = nums1[i];
        dst++, i++;
    }
    while (j < n) {
        nums3[dst] = nums2[j];
        dst++, j++;
    }
    for(int i = 0; i < m + n; i++) {
        nums1[i] = nums3[i];
    }         
}

思路 2

无需开辟新数组，从大到小比较和移动元素。

时间复杂度为 O ( m i n { m , n } ) O(minlbrace m,n rbrace) O(min{m,n})，空间复杂度为 O ( 1 ) O(1) O(1)

void merge(int* nums1, int nums1Size, int m, 
           int* nums2, int nums2Size, int n) {
    int i = m - 1, j = n - 1;
    int dst = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (nums2[j] >= nums1[i]) {
            nums1[dst] = nums2[j];
            dst--, j--;
        }
        else {
            nums1[dst] = nums1[i];
            dst--, i--;
        }
    }
    while (j >= 0) {
        nums1[dst] = nums2[j];
        dst--, j--;
    }
}

比较i和j下标的元素，将其大者放入dst下标的位置。若i先走到0，则将j剩余的元素拷贝到dst。j走到0，标志程序运行结束。

顺序表的缺陷

顺序表即动态增长的数组，动态数组的优缺点是很明显的。

• 缺点：动态扩容时，有时间消耗且产生内存碎片，存在一定程度上的空间浪费。头部和任意位置的插入删除，需要挪动数据。
• 优点：支持随机访问。

增删操作必须要挪动数据，时间消耗不可忽略，这是线性表最大的缺陷。为避免频繁扩容，倍数扩容也会带来不可避免的空间浪费。支持随机访问是线性表的重要的特点，很多算法中要求结构支持随机访问，如二分查找和快排。

而链表利用指针将数据链接起来，结点之间不像数组元素一样强关联。

• 优点：按需合理申请空间，不存在空间浪费。增删结点时无需挪动数据。
• 缺点：结点之间需要通过指针链接。不支持随机访问。

链表不可以通过下标访问任意结点（即随机访问），必须从头结点开始遍历。

 

链表

顺序表采用线性的结构，连续的空间只需要起始地址就可以访问所有元素。顺序表存在的缺陷是顺序表自身特点带来的不可避免的缺陷。为解决这些问题，就出现了一种新的存储形式：链表。

链表的定义及结构

链表是一种物理上的非连续、非顺序的存储结构。数据元素的逻辑顺序通过链表中的指针链接次序实现。

• 逻辑结构：为表现数据元素之间的相互关系而想象出的逻辑图，直观清晰便于理解。

• 存储结构：体现了数据在内存中的存储形式，描述的是内存中实在的物理实体，又称物理结构。

当然这也是最简单的链表结构：单链表。链表包括双头链表、带头不带头链表、循环链表等等。

单链表结构体的定义

typedef int SLTDataType;
typedef struct SListNode {
	//数据域
	SLTDataType data;
	//指针域
	struct SListNode* next;
}SLTNode;

单链表结构体的定义正凸显了它的数据结构。每一个结点包含数据域和指针域，数据域用于存储数据，指针域用于指向下一个结点。通过该指针就可以将所有的结点从头串到尾。

单链表的接口实现

// 动态申请一个结点
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);

单链表尾插头插

由上面单链表插入操作可以看出，操作单链表只能从头结点开始遍历。插入结点后须将前后链接起来。

由于插入函数考虑到结点个数为0的情况，会修改实参plist，故传二级指针&plist。

传二级指针仅是为解决链表为空的情况。也可以选择使用带头结点的方式，只要由头结点之后再尾插就不会更改plist，所以就不用传二级指针。

1. 由于单链表的特点，尾插必然要申请新结点，再将新结点的地址存入尾结点的指针域。

void SListPushBack(SLTNode** pphead, SLTDataType x) {
	SLTNode* newNode = SListNewNode(x);
	//无结点
	if (*pphead == NULL) {
		*pphead = newNode;
	}
	//有结点
	else {
		//找尾结点
		SLTNode* tail = *pphead;
		while (tail->next != NULL) {
			tail = tail->next;
		}
		//尾结点链接
		tail->next = newNode;
	}
}

2. 头插则是申请新节点，先将新结点的地址存入头指针，再将第二个结点phead->next存入新结点的指针域。

void SListPushFront(SLTNode** pphead, SLTDataType x) 
{
	SLTNode* newNode = SListNewNode(x);
	newNode->next = *pphead;
	*pphead = newNode;
}

头插必然要修改指针plist的值，故必然要传头指针的地址。

插入操作需要考虑链表为空的情况。尾插需要遍历链表找尾结点，可能会操作对空指针的解引用，所以要单独考虑。头插不会对空指针进行访问，故头插不需要单独考虑。

单链表尾删头删

1. 尾删，先释放尾结点再置空尾指针，然后置空上一个结点的指针域。

//单链表尾删
void SListPopBack(SLTNode** pphead) {
	//结点个数=0
	assert(*pphead);
	//结点个数=1
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
    //结点个数>1
	else {
		//找尾结点
		SLTNode* tail = *pphead;
        //前驱指针 
        SLTNode* prev = NULL;
        while (tail->next != NULL) {
            prev = tail;
            tail = tail->next;
        }
        //释放尾结点
        free(tail);
        tail = NULL;
        //置空前驱结点指针域
        prev->next = NULL;
	}
}

• 除了将最后一个结点释放掉还要置空上一个结点的指针域，否则会构成野指针访问非法内存。

• 由于单链表的缺陷，不可能通过某结点访问其上一个结点，所以要定义一个前驱指针，在尾指针后移之前将其赋值给前驱指针。如此前驱指针会保持指向尾指针的前一个结点。

• 只要定义前驱指针就必须要考虑链表仅有一个结点的情况，此时不会进入循环prev始终是空指针，最后会操作空指针。

while (tail->next->next) {
    tail = tail->next;
}
free(tail->next);
tail->next = NULL;

若嫌定义前驱指针麻烦，可以只定义一个指针。但本质上都是一样的，仍需考虑结点个数为1的情况。

2. 头删，先将第二个结点赋值给tmp，再将头结点释放，再将tmp赋值给头指针。

void SListPopFront(SLTNode** pphead) {
	//结点个数为0
	assert(*pphead);
	//结点个数>=1
	SLTNode* tmpNode = (*pphead)->next;
	free(*pphead);
	*pphead = tmpNode;
}

由于链表必须从头访问，若先销毁头结点则无法向后遍历，故需要临时变量暂存第二个结点的地址。

尾删要考虑到修改头结点的情况，头删必然会改变头指针，故头删尾删都要传头指针的地址。

删除操作需要考虑链表为空的情况，使用前驱指针需要考虑结点个数为1的情况。否则都会造成对空指针的解引用。

任意位置插入删除

//单链表随机前插
void SListInsertForward(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	SLTNode* newNode = SListNewNode(x);
	//头插时
	if (pos == *pphead) {
		newNode->next = *pphead;
		*pphead = newNode;
	}
	else {
		//找前驱结点
		SLTNode* prev = *pphead;
		while (prev->next != pos) {
			prev = prev->next;
		}
		prev->next = newNode;
		newNode->next = pos;
	}
}

随机前插需要pos位置的前驱结点。因其本身特性，单链表并不适合随机前插，更适合随机后插。前插效率不高也显得更复杂，C++库中也没有前插函数。

//单链表随机后插
void SListInsertAfter(SLTNode* pos, SLTDataType x) {
	SLTNode* newNode = SListNewNode(x);
	//结点个数为0
	if (pos == NULL) {
		pos = newNode;
	}
	else {
		newNode->next = pos->next;
		pos->next = newNode;
	}
}
//查找插入
int main() {
    SLTNode* pos = SListFind(plist, 1);
	if (pos != NULL) {
		SListInsertAfter(pos, 2);
	}
	SListPrint(plist);
}

其他基本接口

void SListPrint(SLTNode* phead) {
	SLTNode* cur = phead;
	while (cur != NULL) {
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}
SLTNode* SListNewNode(SLTDataType x) {
	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newNode == NULL) {
		perror("newNode::malloc");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}
SLTNode* SListFind(SLTNode* phead, SLTDataType x) {
	assert(phead);
	while (phead != NULL) {
		if (phead->data == x) {
			return phead;
		}
		phead = phead->next;
	}
	return NULL;
}
int main() {
	//循环查找
    SLTNode* pos = plist;
	while (pos != NULL) {
    	pos = SListFind(pos, x);
    	if (pos != NULL) {
        	printf("%p-%d-->", pos, pos->data);
        	pos = pos->next;
    	}
	}
    //修改元素
    pos = SListFind(pos, 2);
    if (pos != NULL) {
        pos->data = 3;
    }
}

链表的分类

单链表仍然存在不少的缺陷，单纯使用单链表的增删查改意义不大。

1. 因其存在缺陷，很多OJ题都考察单链表
2. 实际中单链表更多是作为复杂数据结构的子结构，如哈希桶，邻接表等。

使用链表更多使用双向链表存储数据。

链表面试题

Example 1 移除结点

移除结点

删除链表中等于给定值val的所有结点。

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* prev = head;
    struct ListNode* cur = head;
    while (cur != NULL) {
        if (cur->val == val) {
            if (cur == head) {
                head = cur->next;
                free(cur);
                cur = head;
            }
            else {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

Example 2 反转链表

反转链表

反转一个单链表。

struct ListNode* reverseList(struct ListNode* head) {
    int i = 0;
    int val[5000]  = { 0 };
    struct ListNode* cur = head;
    while (cur) {
        val[i] = cur->val;
        i++;
        cur = cur->next;
    }
    cur = head;
    i--;
    while (cur && i >= 0) {
        cur->val = val[i];
        i--;
        cur = cur->next;
    }
    return head;
}

逆置一个链表，不需要真的反转，只需要把结点的数据逆置即可。将结点的数据存入数组，再逆序数组然后依次赋值给各个结点即可。

Example 3 中间结点

中间结点

给定一个带有头结点head的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* cur = head;
    int count = 0;
    while (cur) {
        count++;
        cur = cur->next;
    }
    int i = 0;
    cur = head;
    while (cur) {
        if (i == count / 2) {
            head = cur;
            return head;
        }
        i++;
        cur = cur->next;
    }
    return 0;
}

Example 4 输出结点

输出结点

输入一个链表，输出该链表中倒数第k个结点。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
    // write code here
    int count = 0;
    struct ListNode* cur = pListHead;
    while (cur) {
        count++;
        cur = cur->next;
    }
    cur = pListHead;
    while (cur) {
        if (count == k) {
            return cur;
        }
        count--;
        cur = cur->next;
    }
    return 0;
}