- 顺序表删除和增加元素的时候涉及到大量的元素的移动
- 顺序表因为结构性质的关系，需要一整块连续的内存空间进行操作，而这个在实际情况中是很难满足的。
所以我们需要使用链表来填补这方面的不足。
- 逻辑上相邻的元素，物理上不一定相邻
1、链表初始化
#include <stdio.h>
#include <stdlib.h>
/*
+--------+ +--------+ +--------+
| data | | data | | data |
| 'a' | | 'b' | | 'c' |
| next -------> | next -------> | next -------> NULL
+--------+ +--------+ +--------+
*/
typedef struct node {
char data;
struct node *next;
} node;
node *build(){
node *head = (node *)malloc(sizeof(node));
node *p = head;
for(int i = 0;i<10;i++){
p->data = 'a'+i;
p->next = (node *)malloc(sizeof(node));
p = p->next;
}
p->data = '@';
p->next = NULL;
p = NULL;
return head;
}
int main() {
node *head = build();
node *p = head;
while(p){
printf("%c ",p->data);
p = p->next;
}
return 0; // 正常结束
}
这样的结构对于元素的地址没有要求，并且使用了空间交换了时间的消耗。达到了我们的目的。
2、链表查找&删除
#include <stdio.h>
#include <stdlib.h>
/*
+--------+ +--------+ +--------+
| data | | data | | data |
| 'a' | | 'b' | | 'c' |
| next -------> | next -------> | next -------> NULL
+--------+ +--------+ +--------+
*/
typedef struct node {
char data;
struct node *next;
} node;
node *build(){
node *head = (node *)malloc(sizeof(node));
node *p = head;
for(int i = 0;i<10;i++){
p->data = 'a'+i;
p->next = (node *)malloc(sizeof(node));
p = p->next;
}
p->data = '@';
p->next = NULL;
p = NULL;
return head;
}
//打印链表
void printList(node *head){
node *p = head;
while(p){
printf("%c \n",p->data);
p = p->next;
}
}
//通过下标获取元素
void getItem(node *head,int t,char *c){
node *p = head;
int i = 0;
while(p && i<=t){
if(i ==t){
*c = p->data;
return;
}
p = p->next;
i++;
}
*c = '\0';
}
char removeByIndex(node **head,int t){
node *current = *head;
node *pre = NULL;
int i = 0;
while(current && i<t){
pre = current;
current = current->next;
i++;
}
if(current == NULL){
return '\0';
}
char c = current->data;
if(pre ==NULL){
*head = current->next;
}
else{
pre->next = current->next;
}
free(current);
return c;
}
int main() {
node *head = build();
char c = '\0';
removeByIndex(&head,9);
printList(head);
char cc;
getItem(head,4,&cc);
printf("%c \n",cc);
return 0; // 正常结束
}
这里需要注意的是双指针，如果想修改传入的对象本身，就需要使用双指针。
