单链表（c语言数据结构）

单链表的定义：
由于顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。

单链表的特点：
单链表不要求逻辑上相邻的两个元素在物理位置上也相邻，因此不需要连续的存储空间。单链表是非随机的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。对于每个链表结点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针。

老师的代码如下：

#include
#include


typedef struct LinkNode{
	char data;
	struct LinkNode *next;
}LNode, *LinkList, *NodePtr;


LinkList initLinkList(){
	NodePtr tempHeader = (NodePtr)malloc(sizeof(LNode));
	tempHeader->data = '';
	tempHeader->next = NULL;
	return tempHeader;
}//of initLinkList


void printList(NodePtr paraHeader){
	NodePtr p = paraHeader->next;
	while (p !=NULL){
		printf("%c",p->data);
		p = p->next;
	}//of while 
	printf("rn");
}//of printList


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;
	}//of while
	
	// Step 3.  Now add/link.
	p->next = q;
}//of appendElement


void insertElement(NodePtr paraHeader, char paraChar, int paraPosition){
	NodePtr p,q;
	
	// Step 1.Search to the position.
	p = paraHeader;
	int i;
	for(i=0; i < paraPosition;i++){
		p = p->next;
		if (p == NULL){
			printf("The position %d is beyond the scope of the list.", paraPosition);
			return;
		}// of if
	}//of for i
	
	//Step 2.Construct a new node.
	q = (NodePtr)malloc(sizeof(LNode));
	q->data = paraChar;
	
	//Step 3.Now link.
	printf("linkingrn");
	q->next = p->next;
	p->next = q;
}//of insertElement



void deleteElement(NodePtr paraHeader, char paraChar){
	NodePtr p,q;
	p = paraHeader;
	while ((p->next != NULL)&&(p->next->data != paraChar)){
		p = p->next;
	}//of while
	
	if (p->next == NULL){
		printf("Cannot delete %crn", paraChar);
		return;
	}//of if
	
	q = p->next;
	p->next = p->next->next;
	free(q); 
}//of deleteElement


void appendInsertDeleteTest(){
	// Step 1.Initialize an empty list.
	LinkList tempList = initLinkList();
	printList(tempList);
	
	// Step 2. Add some characters.
	appendElement(tempList,'H');
	appendElement(tempList,'e');
	appendElement(tempList,'l');
	appendElement(tempList,'l');
	appendElement(tempList,'o');
	appendElement(tempList,'!');
	printList(tempList);
	
	//Step 3.Delete some characters (the first occurrence).
	deleteElement(tempList,'e');
	deleteElement(tempList,'a');
	deleteElement(tempList,'o');
	printList(tempList);
	
	// Step 4.Insert to a given position.
	insertElement(tempList,'o',1);
	printList(tempList);
}//of appendInsertDeleteTest


void basicAddressTest(){
	LNode tempNode1, tempNode2;
	
	tempNode1.data = 4;
	tempNode1.next = NULL;
	
	tempNode1.data = 6;
	tempNode2.next = NULL;
	
	printf("The first node: %d, %d, %drn",&tempNode1, &tempNode1.data, &tempNode1.next);
	printf("The second node: %d, %d, %drn",&tempNode2, &tempNode2.data, &tempNode2.next);
	
	tempNode1.next = &tempNode2;
}//of basicAddressTest


int main(){
	appendInsertDeleteTest();
}//of all

我的代码如下：

创建结构体

typedef struct LinkNode{
	char data;
	struct LinkNode *next;
}LNode, *LinkList, *NodePtr;

创建头结点 (初始化）

LinkList initLinkList(){
	NodePtr tempHeader = (NodePtr)malloc(sizeof(LNode));//分配内存 
	tempHeader->data = '';
	tempHeader->next = NULL;
	return tempHeader;
}

打印线性表

void printList(NodePtr paraHeader){
	NodePtr p = paraHeader->next;
  
	for(;p!=NULL;){
	    printf("%c",p->data);
		p = p->next;
		}
	printf("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 headcreatElement(NodePtr paraHeader, char paraChar) {
	NodePtr p;
	paraHeader->next = NULL;
	int i;
	for (i=0;i<10;i++){
		p = (NodePtr)malloc(sizeof(LNode));
		p->data = i;
		p->next = paraHeader->next;
		paraHeader->next = p;
	}

在给定位置插入一个元素

void insertElement(NodePtr paraHeader, char paraChar, int paraPosition){
	NodePtr p,q;
	
	//判断位置是否合法 
	p = paraHeader;
	int i;
	for(i=0; i < paraPosition;i++){
		p = p->next;
		if (p == NULL){
			printf("位置超出列表范围！n");
			return;
		}
	}
	
	//构造一个新节点 
	q = (NodePtr)malloc(sizeof(LNode));
	q->data = paraChar;
	
	//链接
	q->next = p->next;
	p->next = q;
}

删除元素

void deleteElement(NodePtr paraHeader, char paraChar){
	NodePtr p,q;
	p = paraHeader;
   
	for(;(p->next != NULL)&&(p->next->data != paraChar);){
		p = p->next;
	}
	
	//判断元素是否存在于线性表中 
	if (p->next == NULL){
		printf("删除失败！n");
		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,'W');
	appendElement(tempList,'o');
	appendElement(tempList,'r');
	appendElement(tempList,'l');
	appendElement(tempList,'d');
	appendElement(tempList,'!');
	printList(tempList);//打印线性表 
	
	//删除一些字符 
	deleteElement(tempList,'e');
	deleteElement(tempList,'a');//找不到a，不能删除 
	deleteElement(tempList,'o');
	deleteElement(tempList,'l');
	deleteElement(tempList,'w');
	printList(tempList);//打印线性表 
	
	//插入到指定位置 
	insertElement(tempList,'o',1);
	insertElement(tempList,'o',10);
	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, %drn",&tempNode1, &tempNode1.data, &tempNode1.next);
	printf("The second node: %d, %d, %drn",&tempNode2, &tempNode2.data, &tempNode2.next);
	
	tempNode1.next = &tempNode2;
}

测试结果·：

Helloworld!
删除失败！
Hlorld!
位置超出列表范围！
Hoolorld!
The first node: 6487520, 6487520, 6487528
The second node: 6487504, 6487504, 6487512

全部代码：

#include
#include

//创建结构体 
typedef struct LinkNode{
	char data;
	struct LinkNode *next;
}LNode, *LinkList, *NodePtr;

//创建头结点 (初始化） 
LinkList initLinkList(){
	NodePtr tempHeader = (NodePtr)malloc(sizeof(LNode));//分配内存 
	tempHeader->data = '';
	tempHeader->next = NULL;
	return tempHeader;
}

//打印线性表
void printList(NodePtr paraHeader){
	NodePtr p = paraHeader->next;

	for(;p!=NULL;){
	    printf("%c",p->data);
		p = p->next;
		}
	printf("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;
	int i;
	for(i=0; i < paraPosition;i++){
		p = p->next;
		if (p == NULL){
			printf("位置超出列表范围！n");
			return;
		}
	}
	
	//构造一个新节点 
	q = (NodePtr)malloc(sizeof(LNode));
	q->data = paraChar;
	
	//链接
	q->next = p->next;
	p->next = q;
}

//头插法



//删除元素 
void deleteElement(NodePtr paraHeader, char paraChar){
	NodePtr p,q;
	p = paraHeader;
 
	for(;(p->next != NULL)&&(p->next->data != paraChar);){
		p = p->next;
	}
	
	//判断元素是否存在于线性表中 
	if (p->next == NULL){
		printf("删除失败！n");
		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,'w');
	appendElement(tempList,'o');
	appendElement(tempList,'r');
	appendElement(tempList,'l');
	appendElement(tempList,'d');
	appendElement(tempList,'!');
	printList(tempList);//打印线性表 
	
	//删除一些字符 
	deleteElement(tempList,'e');
	deleteElement(tempList,'a');//找不到a，不能删除 
	deleteElement(tempList,'o');
	deleteElement(tempList,'l');
	deleteElement(tempList,'w');
	printList(tempList);//打印线性表 
	
	//插入到指定位置 
	insertElement(tempList,'o',1);
	insertElement(tempList,'o',10);
	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, %drn",&tempNode1, &tempNode1.data, &tempNode1.next);
	printf("The second node: %d, %d, %drn",&tempNode2, &tempNode2.data, &tempNode2.next);
	
	tempNode1.next = &tempNode2;
}
//入口 
int main(){
	appendInsertDeleteTest();
	basicAddressTest();
}