西柚数据结构第三次课——单链表

西柚数据结构第三次课——单链表

 单链表的元素插入与删除、初始化、遍历、尾部添加元素、插入元素、删除元素

#include<stdio.h>
#include<malloc.h>
/** linked list of characters. the key is data.*/
typedef struct LinkNode {char data;struct LinkNode* next;
}LNode, * LinkList, * NodePtr;/** Initialize the list with a header.* @return the pointer to the header.*/
LinkList initLinkList() {NodePtr tempHeader = (NodePtr)malloc(sizeof(LNode));tempHeader->data = '';tempHeader->next = NULL;return tempHeader;
}/** Print the list.* @param oaraHeader The header of the list.
*/
void printfList(NodePtr paraHeader) {NodePtr p = paraHeader->next;while (p != NULL) {printf("%c", p->data);p = p -> next;}printf("rn");
}/*
* Add an element to the tail.
* @param paraHeader the header of the list.
* @param paraChar the given char.
*/
void appendElement(NodePtr paraHeader, char paraChar) {NodePtr p, q;//step 1.Construct a new node.q = (NodePtr)malloc(sizeof(LNode));q->data = paraChar;q->next = NULL;//step 2.search to the tail.(尾）p = paraHeader;while (p->next != NULL) {p = p->next;}//w add/link.p->next = q;
}/** insert an element to the given position.* @param paraHeader the header of the list.* @param paraChar the given char.* @param paraposition the given position.*/
void insertElement(NodePtr paraHeader, char paraChar, int paraPosition) {NodePtr p, q;//step 1.search to the position,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;}}//struct a new node.q = (NodePtr)malloc(sizeof(LNode));q->data = paraChar;//w link.printf("linkingrn");q->next = p->next;p->next = q;
}/** Delete an element from the list.* @param paraHeader the header of the list.* @param paraChar the given char.*/
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 %crn", paraChar);return;}q = p->next;p->next = p->next->next;free(q);
}/**unit test. */
void appendInsertDeleteTest() {//step 1.Initialize an empty list.LinkList tempList = initLinkList();printfList(tempList);//step 2.add some characters.appendElement(tempList, 'H');appendElement(tempList, 'e');appendElement(tempList, 'l');appendElement(tempList, 'l');appendElement(tempList, 'o');appendElement(tempList, '!');printfList(tempList);//step 3.delete some characters(the first occurrence)deleteElement(tempList, 'e');deleteElement(tempList, 'a');deleteElement(tempList, 'o');printfList(tempList);//step 4.insert to a given position.insertElement(tempList, 'o', 1);printfList(tempList);
}/** adderss test: beyond the book.*/
void basicAddressTest() {LNode tempNode1, tempNode2;tempNode1.data =  = NULL;tempNode2.data =  = NULL;printf("The first node:%d,%d,%drn", &tempNode1, &tempNode1.data, &);printf("The second node:%d,%d,%drn", &tempNode2, &tempNode2.data, &); = &tempNode2;
}/** the entrance.*/
int main() {appendInsertDeleteTest();
}

Hello!
Cannot delete a
Hll!
linking
Holl!

单链表是一种数据结构，它由一个节点序列组成，每个节点包含两个部分：数据和指向下一个节点的指针。单链表中只能向一个方向遍历，即从头节点开始，依次向后遍历。该数据结构可以用于实现栈、队列等数据结构，也可用于解决一些具有类似链式结构的问题。由于单链表的节点只包含一个指向下一个节点的指针，因此在插入、删除节点时较为方便，但是在查找节点时需要遍历整个链表。

在链式存储中，结点之间的存储单元地址是不连续的。链式存储中每个结点都包含两个部分：存储元素本身的数据域和存储结点地址的指针域。
 

数据结构单链表代码实现 1.初始化单链表 2.头插法创建单链表 3.尾插法创建单链表 4.按序号查找值，按值查找表结点 5.求表长，插入结点 6.删除结点，输出单链表 7.主函数 8.效果

输出单链表的程序设计思想如下：

（1）定义一个结点结构体指针变量 p

（2）让 p 指向链表的第一个结点即头指针所指向的结点。

（3）使用当型循环，循环的条件是 p所指向的结点成员 point 不是NULL，在循环体中执行的下面的操作：

输出指针变量 p 所指向结点的数据；

让指针变量 p 指向链表中的下一个结点；

继续下一轮的循环。