双向链表 创建、删除、反转、插入
//struct
#include <stdio.h>
#include <stdlib.h>
#include <string.h> /**********************双向链表************************************/ typedef struct Student_Double
{
char name[];
int point;
struct Student_Double *preStu;
struct Student_Double *nextStu;
} StudentDouble; //创建双向链表
StudentDouble *CreateDoubleLinkTable(void){
int i = ;
StudentDouble *head = NULL;
head = (StudentDouble *)malloc(sizeof(StudentDouble));
head->name[]='\0';
head->point = ;
head->preStu = NULL;
head->nextStu = NULL; StudentDouble *temp,*currentNode;
currentNode=head;
while (i<=) {
temp = (StudentDouble *)malloc(sizeof(StudentDouble));
strncpy(temp->name,"Node",sizeof(temp->name));
temp->point = i;
temp->preStu = currentNode;
temp->nextStu = NULL; currentNode->nextStu = temp; currentNode = temp;
i++;
} return head;
}
//正序查询
StudentDouble * SelectDoubleLinkTableFormHead(StudentDouble *head){
StudentDouble *endNode = NULL;
StudentDouble *next = head->nextStu;
if (next == NULL) {
printf("查询失败,不是链式结构\n");
exit();
} int i =;
while (next) {
printf("index %d; studentName is %s; point is %d\n",i+,next->name,next->point);
if (next->nextStu == NULL) {
endNode = next;
printf("双向链表尾节点：%d \n",endNode->point);
}
next=next->nextStu;
i++;
}
return endNode;
}
//反序查询
void SelectDoubleLinkTableFormEnd(StudentDouble *end){ StudentDouble *pre = end->preStu;
if (pre==NULL) {
printf("查询失败,不是链式结构\n");
exit();
}
pre = end;
int i = ;
while (pre) {
if (pre->name[]=='\0') {
//头链
break;
}
printf("index %d; studentName is %s; point is %d\n",i+,pre->name,pre->point);
pre = pre->preStu;
i++;
}
} //双向链表 插入节点 上一节点序号|插入节点名
StudentDouble *insertStudentDoubleLinkTable(StudentDouble *head,char *content){
if (!content) {
exit();
}
//分割字符串
char *token;
char nodeName[];
int nodeIndex;
token = strtok(content,"|");
int i = ;
while (token != NULL) {
if (i>) {
strncpy(nodeName,token,sizeof(char[]));
}else{
nodeIndex = atoi(token);
}
token = strtok(NULL,"|");
i++;
} //查找节点
StudentDouble *next = head->nextStu;
if (next==NULL) {
printf("不是链式结构");
exit();
}
int search = ;
StudentDouble *searchNode = NULL;
while (next) {
if (next->point == nodeIndex) {
search = ;
searchNode = next;
}
next = next->nextStu;
}
if (search==) {
printf("没有找到节点序号为%d 的节点",nodeIndex);
exit();
}
//插入节点
StudentDouble *nextLinkTable = searchNode->nextStu;
//创建新节点
StudentDouble *new = (StudentDouble *)malloc(sizeof(StudentDouble));
strncpy(new->name,nodeName,sizeof(new->name));
new->point = ;//这两随机去的数。
new->preStu = searchNode;
new->nextStu = nextLinkTable; searchNode->nextStu = new; return head;
} //双向链表 删除节点
StudentDouble *DelegateDoubleLinkTable(StudentDouble *head,int nodeIndex){
//查找节点
StudentDouble *next = head->nextStu;
if (next==NULL) {
printf("不是链式结构");
exit();
}
int search = ;
StudentDouble *searchNode = NULL;
while (next) {
if (next->point == nodeIndex) {
search = ;
searchNode = next;
}
next = next->nextStu;
}
if (search==) {
printf("没有找到节点序号为%d 的节点",nodeIndex);
exit();
} StudentDouble *preNode = searchNode->preStu;
StudentDouble *nextNode = searchNode->nextStu; preNode->nextStu = nextNode;
nextNode->preStu = preNode; //释放
free(searchNode);
return head;
} int main(void){
char sf[];
int num;
/**
* 创建双向循环链表
*/
StudentDouble *head = NULL;
StudentDouble *end = NULL;
printf("开始创建双向链表Y|N \n");
scanf("%s",sf);
if (strcmp(sf,"Y")==) {
head = CreateDoubleLinkTable();
}
printf("正序查询双向链表Y|N \n");
scanf("%s",sf);
if (strcmp(sf,"Y")==) {
end = SelectDoubleLinkTableFormHead(head);
} printf("反序查询双向链表Y|N \n");
scanf("%s",sf);
if (strcmp(sf,"Y")==) {
printf("双向链表尾节点：%d \n",end->point);
if (end->point == ) {
printf("双向链表反向查询\n");
SelectDoubleLinkTableFormEnd(end);
}
} printf("插入双向链表 如：4(上一个节点序号)|name(要插入的节点名)\n");
scanf("%s",sf);
head = insertStudentDoubleLinkTable(head,sf);
SelectDoubleLinkTableFormHead(head); printf("删除双向链表节点 输入要删除节点序号\n");
scanf("%d",&num);
head = DelegateDoubleLinkTable(head,num);
SelectDoubleLinkTableFormHead(head); return ;
}
双向链表反转： 和前面 单向链表反转 同样思路。
遍历链表 ， 游标指针为当前遍历到的节点currentNode。 后续节点 nextNode。新链表 newLinkTable 初始为NULL;
思路如下：
//反转 双向链表
StudentDouble * ReversionDoubleLinkTable(StudentDouble *head){
StudentDouble *next = head->nextStu;
if (next==NULL) {
printf("不是链式结构");
exit();
} StudentDouble *currentNode,*nextNode,*newLinkTable;
currentNode = next;
newLinkTable = NULL;
while (currentNode) { //保持后续节点
nextNode = currentNode->nextStu;
//断开
currentNode->nextStu = newLinkTable;
currentNode->preStu = NULL;
if (newLinkTable !=NULL) {
newLinkTable->preStu = currentNode;
}
//保存游标节点
newLinkTable = currentNode;
//重置游标节点
currentNode = nextNode;
} StudentDouble *newHead = (StudentDouble*)malloc(sizeof(StudentDouble));
newHead->name[]='\0';
newHead->point = ;
newHead->nextStu = newLinkTable;
newHead->preStu = NULL;
newLinkTable->preStu = newHead; return newHead;
}
int main(void){
char sf[];
int num;
/**
* 创建双向循环链表
*/
StudentDouble *head = NULL;
StudentDouble *end = NULL;
printf("开始创建双向链表Y|N \n");
scanf("%s",sf);
if (strcmp(sf,"Y")==) {
head = CreateDoubleLinkTable();
}
printf("正序查询双向链表Y|N \n");
scanf("%s",sf);
if (strcmp(sf,"Y")==) {
end = SelectDoubleLinkTableFormHead(head);
}
printf("反序查询双向链表Y|N \n");
scanf("%s",sf);
if (strcmp(sf,"Y")==) {
printf("双向链表尾节点：%d \n",end->point);
if (end->point == ) {
printf("双向链表反向查询\n");
SelectDoubleLinkTableFormEnd(end);
}
}
printf("反转双向链表 Y|N \n");
scanf("%s",sf);
if (strcmp(sf,"Y")==) {
head = ReversionDoubleLinkTable(head);
printf("正序查询双向链表Y|N \n");
scanf("%s",sf);
if (strcmp(sf,"Y")==) {
end = SelectDoubleLinkTableFormHead(head);
}
printf("反序查询双向链表Y|N \n");
scanf("%s",sf);
if (strcmp(sf,"Y")==) {
printf("双向链表尾节点：%d \n",end->point);
if (end->point == ) {
printf("双向链表反向查询\n");
SelectDoubleLinkTableFormEnd(end);
}
}
}
return ;
}