1.写在前面

本文主要是用于记录单链表章节的学习心得,在闵老代码的基础上进行不断的完善,以达到学习认识单链表的目的。可能仍有疏漏之处,还望批评指正。

2.主要组成部分

1).定义单链表类型

本步骤的目的在于,定义后续的表,以及代替表进行工作的的指针。

代码实现如下:

“”

typedef struct LinkNode

{

char data;

struct LinkNode *next;

}LNode,*LinkList,*NodePtr;

“”

2)表的初始化

分配储存空间,初始化链表中量。

代码实现如下:

“”

LinkList initLinkList()

{

NodePtr tempHeader=(NodePtr)malloc(sizeof(LNode));

tempHeader->data=’\0′;

tempHeader->next=NULL;

return tempHeader;

}

“”

3)表的建立

有两种方法进行表的建立,头插法子与尾插法

代码实现如下:

(1)尾插法

“”

void tailCreatList(LinkList L)
{
LinkList p, q;
q = L;
for (int i = 0; i < 10; i++) {
p = (LNode*)malloc(sizeof(LNode));
p->data = i;
q->next = p;
q = p;
}
q->next = NULL;
}

“”

(2)头插法

代码实现如下:

“”

void headCreatList(LinkList L)
{
LinkList p;
L->next = NULL;
for (int i = 0; i < 10; i++) {
p = (LNode*) malloc(sizeof(LNode));
p->data = i;
p->next = L->next;
L->next = p;
}
}

“”

4)表的显示

显示表中的内容,该过程用循环来实现。

代码实现如下:

“”

void printList(NodePtr paraHeader)

{

NodePtr p=paraHeader->next;

while(p!=NULL)

{

printf(“%c”,p->data);

p=p->next;

}// Of while

printf(“\r\n”);

}

“”

5)表的插入

具体过程,好比小朋友手拉手站成一排,此时来了一个新的小朋友,需要在两个同学间站立,那么就要两个同学先松手,然后再和新的那个小朋友拉手(原谅我匮乏的语文水平,实在找不到更好的比喻了)

代码实现:

“”

void insertElement(NodePtr paraHeader, char paraChar, int paraPosition){

NodePtr p, q;

p = paraHeader;

for (int i = 0; i < paraPosition; i ++) {

p = p->next;

if (p == NULL) {

printf(“The position %d is beyond the scope of the list.”, paraPosition);

return;

}

}

q = (NodePtr)malloc(sizeof(LNode));

q->data = paraChar;

printf(“linking\r\n”);

q->next = p->next;

p->next = q;

}

“”

6)表的删除

还是用刚才那个例子来做比喻(笑哭),有个小朋友要想脱离出去,那么就需要和左右两边的同学,相互间松开手,然后左右两边的同学再相互拉手,以此来保持表的完整性

(1).删除指定的位置处的元素值

代码实现如下:

int deleteElementbyPostion(LinkList L, int postion)
{
LinkList p, q;
p = L;

if(postion < 0)
{
printf(“fail!\n”);
return -1;
}
for(int i = 0; i< postion; i++)
{
p = p->next;
if(p == NULL){
printf(“fail!\n”);
return -1;
}
}
int az = p->next->data;
q = (LNode*)malloc(sizeof(LNode));
q = p->next;
p->next = p->next->next;
if(p->next == NULL)
{
Tail = p;
}
free(q);
printf(“sucess,and the delet data is %d\n”, x);
return x;
}

(2)删除指定的元素

代码实现如下:

‘“

void deleteElement(NodePtr paraHeader, char paraChar){

NodePtr p, q;

p = paraHeader;

while ((p->next != NULL) && (p->next->data != paraChar)){

p = p->next;

}

if (p->next == NULL) {

printf(“Cannot delete %c\r\n”, paraChar);

return;

}

q = p->next;

p->next = p->next->next;

free(q);

}

””

以及:

尾删

头删

7).完整代码实现

#include

#include

typedef struct LinkNode{

char data;

struct LinkNode *next;

}LNode,*LinkList,*NodePtr;

//定义单链表

LinkList initLinkList()

{

NodePtr tempHeader=(NodePtr)malloc(sizeof(LNode));

tempHeader->data=’\0′;

tempHeader->next=NULL;

return tempHeader;

}

//初始化单链表

void printList(NodePtr paraHeader)

{

NodePtr p=paraHeader->next;

while(p!=NULL)

{

printf(“%c”,p->data);

p=p->next;

}

printf(“\r\n”);

}

//定义显示函数

void appendElement(NodePtr paraHeader, char paraChar){

NodePtr p, q;

q = (NodePtr)malloc(sizeof(LNode));

q->data = paraChar;

q->next = NULL;

p = paraHeader;

while (p->next != NULL) {

p = p->next;

}

p->next = q;

}

//赋值

void insertElement(NodePtr paraHeader, char paraChar, int paraPosition){

NodePtr p, q;

p = paraHeader;

for (int i = 0; i < paraPosition; i ++) {

p = p->next;

if (p == NULL) {

printf(“The position %d is beyond the scope of the list.”, paraPosition);

return;

}

}

q = (NodePtr)malloc(sizeof(LNode));

q->data = paraChar;

printf(“linking\r\n”);

q->next = p->next;

p->next = q;

}

//定义插入函数

void deleteElement(NodePtr paraHeader, char paraChar){

NodePtr p, q;

p = paraHeader;

while ((p->next != NULL) && (p->next->data != paraChar)){

p = p->next;

}

if (p->next == NULL) {

printf(“Cannot delete %c\r\n”, paraChar);

return;

}

q = p->next;

p->next = p->next->next;

free(q);

}

//定义删除函数

void appendInsertDeleteTest(){

LinkList tempList = initLinkList();

printList(tempList);

appendElement(tempList, ‘H’);

appendElement(tempList, ‘e’);

appendElement(tempList, ‘l’);

appendElement(tempList, ‘l’);

appendElement(tempList, ‘o’);

appendElement(tempList, ‘!’);

printList(tempList);

deleteElement(tempList, ‘e’);

deleteElement(tempList, ‘a’);

deleteElement(tempList, ‘o’);

printList(tempList);

insertElement(tempList, ‘o’, 1);

printList(tempList);

}

//插入函数的测试样例

void basicAddressTest(){

LNode tempNode1, tempNode2;

tempNode1.data = 4;

tempNode1.next = NULL;

tempNode2.data = 6;

tempNode2.next = NULL;

printf(“The first node: %d, %d, %d\r\n”,

&tempNode1, &tempNode1.data, &tempNode1.next);

printf(“The second node: %d, %d, %d\r\n”,

&tempNode2, &tempNode2.data, &tempNode2.next);

tempNode1.next = &tempNode2;

}

//删除函数的测试样例

int main(){

appendInsertDeleteTest();

}

//在main函数中调用