数据结构---链表(重点)

链表的节点
1–>2–>3–>NULL

Node*first =0xCC; //0xCC为第一个结点的地址

结点地址{value,next}
0xCC{1,0xFF}
0xFF{2,0x44}
0x44{3,NULL}

typedef struct Node
{
int value;
struct Node *next;//保存着下一个结点的地址,找到最后一个为NULL时结束
}Node;

初始化

//初始化链表就是一条空链表,一个节点都没有的链表,即first=NULL
void SListInit(Node **){
*ppFirst = NULL;
}

头插
此时firs=NULL
如果头插数字为4,假设其地址为0x88
则应为0x88{4,NULL}
以下的代码可以应对链表为空和不为空的情况

void SListPushFront(Node **ppFirst, int v){
Node *node = (Node*)malloc(sizeof(Node));
node->value = v;
node->next = *ppFirst;
*ppFirst = node;
}

头删
first
1–>2–>3–>NULL
2–>3–>NULL
记的释放1的空间
比如原来是0x88{1,0xCC}
**ppFirst=0x88;
将1释放掉的同时,留下0xCC,最终目的是
**ppFirst=0xCC;

void SListPopFront(Node **ppFirst){
assert(*ppFirst != NULL);//一个结点都没有的话,无法进行删除
Node *next = (*ppFirst)->next;//找一个地方存放1的地址,防止释放丢失
free(*ppFirst);
*ppFirst = next;
}

尾插
first
1–>2–>3–>NULL
0xCC{1,0xFF}
0xFF{2,0xDD}
0xDD{3,NULL}

比如要插入的结点为4,
如node=0x88 0x88{4,?}
则最终目的是0x88{4,NULL} 0xDD{3,0x88}

可以采用遍历的方法
//cur为最后一个结点
//当cur的下一个地址不为空时继续循环,所以有cur->next!=NULL
for(Node*cur=first;cur->next!=NULL;cur=cur->next){
}
或者while循环

void SListPushBack(Node **ppfirst,int v){
//申请新空间
Node *node = (Node*)malloc(sizeof(Node));
node->value = v;
node->next = NULL;//node是新的最后一个结点,所以next=NULL
if (*ppfirst==NULL){
*ppfirst = node;
//链表为空,没有任何结点
*ppfirst = node;
}
else
{
//找最后一个结点,最后一个结点的next一定是NULL
Node *cur = *ppfirst;
while(cur->next!=NULL){
cur = cur->next;
}
//cur就是最后一个结点
Node *node = (Node*)malloc(sizeof(Node));
node ->value = v;
node->next = NULL;
//让原来最后一个结点的next=新的节点
cur ->next = node;
}
}

尾删
first
1–>2–>3–>NULL
0xCC{1,0xFF}
0xFF{2,0xDD}
0xDD{3,NULL}
即将 0xFF{2,0xDD}变为 0xFF{2,MULL}
0xDD{3,NULL}删去
找到倒数第二个结点
即为cur->next->next ==NULL

void SListPopBack(Node **ppFirst){
//当空链表时,无法进行尾删操作,退出
assert(*ppFirst != NULL);
//当链表只有一个结点时的情况
if ((*ppFirst)->next==NULL){
free(*ppFirst);
*ppFirst = NULL;
return;
}
//当链表的结点数大于1时的情况
//找到倒数第二个结点
//即为cur->next->next == NULL
Node *cur = *ppFirst;
while (cur->next->next==NULL){
cur = cur->next;
}
//释放最后一个结点
free(cur->next);
cur->next = NULL;
}

查找

 1-->2-->3-->NULL
[
)
查找一直找到NULL的位置

Node * SListFind(const Node *first,int v){
for (Node*cur = first; cur != NULL;cur=cur->next){
if (cur->value==v){
return cur;
}
}
return NULL;
}

释放

void SListDestroy(Node *first){
Node *next;
for (Node *cur = first; cur != NULL;cur=next){
next = cur->next;
free(cur);
}
}

在指定位置pos后面做插入
pos一定是链表中的结点

void SListInsertAfter(Node *pos,int v){
Node *node = (Node*)mallloc(sizeof(Node));
node->value = v;
node->next = pos->next;
pos->next = node;
}

在指定位置pos后面做删除
pos一定是链表中的结点

void SListEraseAfter(Node *pos){
Node *next = pos->next;
pos->next = pos->next->next;
free(next);
}

最后

以上就是妩媚诺言为你收集整理的数据结构---链表(重点)的全部内容，希望文章能够帮你解决数据结构---链表(重点)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。