[链表]带头结点的链表的创建、查找、插入、删除

[链表]带头结点的链表的创建、查找、插入、删除

C代码如下:

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
int data;
struct node* next;// 这个地方注意结构体变量的定义规则
} Node, *PNode;

Node* createLinklist(int length)
{
int i = 0;
PNode pHeader = NULL;
PNode pTail = NULL;
PNode pTemp = NULL;
printf(“create\n”);

pHeader = (PNode)malloc(sizeof(Node));// 申请头结点
if (!pHeader)
{
exit(-1);
}
pHeader->next = NULL;

for (i = 0; i < length; i++)
{
pTemp = (PNode)malloc(sizeof(Node));// 用malloc要包含头文件
if (!pTemp)
{
exit(-1);
}
pTemp->data = i*10;
pTemp->next = NULL;
if (!pHeader->next)
{
// 第一个结点是空的,则先连接第一个结点
pHeader->next = pTemp;
}
else
{
pTail->next = pTemp;
}
pTail = pTemp;
}
return pHeader;
}

Node* search(PNode pHeader, int k)
{
PNode p = pHeader->next;
int i = 1;
printf(“search\n”);
while(p && (i < k))
{
p = p->next;
i++;
}
if (p && (i == k)) // 这步的i == k是必须的,
// 因为如果一开始的时候 i就 >= k并且pHeader->next还不为NULL这一步就会必过,导致返回的是第一个元素的值
{
return p;
}
return NULL;
}

int insert(PNode pHeader, PNode pNew, int k)
{
PNode p = NULL;
printf(“insert\n”);
if ( 1 == k )
{
p = pHeader;
}
else
{
printf(“==>”);
p = search(pHeader, k-1);
}
if (p)
{
// 带头结点和不带头结点的主要区别之一就在这
// 如果不带头结点,那么在第一个位置插入结点的操作应该是
// pNew->next = p;
// p = pNew;
// 带头结点的操作如下
pNew->next = p->next;
p->next = pNew;
return 1;
}
return 0;
}

int deleteNode(PNode pHeader, int k)
{
PNode p = NULL;
printf(“deleteNode\n”);
if (1 == k)
{
p = pHeader->next;
}
else
{
printf(“==>”);
p = search(pHeader, k-1);
}
if (p && p->next)
{
// 不带头结点的操作时删除第一个结点的操作
// Node* temp = p;
// p = p->next;
// free(temp);
// 带头结点的操作如下
PNode temp = p->next;
p->next = temp->next;
free(temp);
return 1;
}
else
{
printf(“Not Found\n”);
return 0;
}
}

void print(PNode pHeader)
{
PNode p = pHeader->next;
printf(“print\n “);
while(p)
{
printf(“%4d “, p->data);
p = p->next;
}
putchar(‘\n’);
}

void freeList(PNode pH)
{
PNode p = NULL;
printf(“freeList\n”);
while(NULL != pH)
{
p = pH;
pH = pH->next;
printf(“%4d be freed\n”, p->data);
free(p);
}
}

int main(void)
{
PNode pHeader = NULL;// C和C++中判断指针为空都是用NULL宏(全大写)
PNode pNew = NULL;
PNode result = NULL;
pHeader = createLinklist(10);
print(pHeader);
result = search(pHeader, 5);
if ( result )
{
printf(“%d\n”, result->data);
}
else
{
printf(“Not Found\n”);
}
pNew = (PNode)malloc(sizeof(Node));
if (!pNew)
{
exit(-1);
}
pNew->data = 100;
pNew->next = NULL;
insert(pHeader, pNew, 5);
print(pHeader);
deleteNode(pHeader, 12);
print(pHeader);
freeList(pHeader);
return 0;
}

标签