老师版
#include <stdio.h>
#include <stdlib.h> // 定于Node数据类型
struct Node
{
int data; // 数据域
struct Node *next; // 指针域
}; // 创建一个单链表,并把head节点返回;
struct Node* createLinkList(void);
struct Node* createLinkList(void)
{
struct Node *head = NULL;
struct Node *tail = NULL;
struct Node *temp = NULL; int data; scanf("%d",&data);
// data 不等于0
while (data)
{
// malloc 函数申请内存
temp = (struct Node *)malloc(sizeof(struct Node));
temp->data = data;
temp->next = NULL; if (head == NULL)
{
head = temp;
tail = temp;
}
else
{
tail->next = temp;
tail = temp;
} scanf("%d",&data);
} return head;
} // 输出链表元素
void printLinkList(struct Node *head);
void printLinkList(struct Node *head)
{
struct Node *p = head;
if (p == NULL)
{
return;
}
else
{
while (p)
{
printf("%d-》",p->data);
// 指针重定向
p = p->next;
}
}
} // 计算链表的长度
int count(struct Node *head);
int count(struct Node *head)
{
int count = ;
struct Node *p = NULL;
p = head;
while (p)
{
count++;
p = p->next;
} return count;
} int getNode(struct Node *head,int pos);
int getNode(struct Node *head,int pos)
{
if (pos > count(head))
{
return ;
} struct Node *p = head;
for (int i = ; i < pos; i++)
{
p = p->next;
} return p->data;
} void insertIntoHead(struct Node **h,int value);
void insertIntoHead(struct Node **h,int value)
{
struct Node *temp = NULL;
temp = (struct Node *)malloc(sizeof(struct Node));
temp->data = value;
temp->next = NULL; if (h == NULL)
{
*h = temp;
}
else
{
temp->next = *h;
*h = temp;
}
} //2、把单链表中第pos个结点的值修改为x的值,若修改成功返回1,否则返回0
int modifyNode(struct Node *head,int pos,int x);
int modifyNode(struct Node *head,int pos,int x)
{
// 如果链表为空,或者pos 超出链表长度
if (head == NULL || pos > count(head))
{
return ;
} struct Node *p = NULL;
p = head;
for (int i = ; i < pos; i++)
{
p = p->next;
} p->data = x;
return ;
} void insertIntoTail(struct Node **head,int value);
void insertIntoTail(struct Node **head,int value)
{
struct Node *tmp = NULL;
tmp = malloc(sizeof(struct Node));
tmp->data = value;
tmp->next = NULL;
if (*head == NULL)
{
*head = tmp;
}
else
{
struct Node *p;
// 定位最后一个节点
p = *head;
while (p->next)
{
p = p->next;
}
// 将申请的tmp加到链表后面
p->next = tmp;
}
} int insertInto(struct Node **head,int pos,int value);
int insertInto(struct Node **head,int pos,int value)
{
if (*head == NULL)
{
// 在第一个位置添加一个节点
insertIntoHead(head, value);
return ;
}
if (pos > count(*head))
{
// 在最后一个位置添加一个节点
insertIntoTail(head, value);
return ;
}
// 申请一个节点
struct Node *tmp;
tmp = malloc(sizeof(struct Node));
tmp->data = value;
tmp->next = NULL;
if (tmp==NULL)//tmp 申请内存失败
{
return ;
}
else
{
// 声明一个辅助指针
struct Node *p;
p = *head;
// 定位辅助指针,指向pos位置前一个节点
for (int i = ; i<pos-; i++)
{
p = p->next;
}
tmp->next = p->next;
p->next = tmp;
return ;
}
} void insertIntoSortedList(struct Node **head,int value);
void insertIntoSortedList(struct Node **head,int value)
{
// 如果是链表为空,在第一个位置添加
if (*head == NULL)
{
insertIntoHead(head, value);
return;
} // 记录要添加元素的位置
int pos = ;
struct Node *p = NULL;
p = *head;
while (p)
{
if (p->data < value)
{
pos++;
p = p->next;
}
else
{
// 跳出循环
break;
}
} insertInto(head, pos, value);
} int deleteFirstNode(struct Node **head);
int deleteFirstNode(struct Node **head)
{
if (*head == NULL)
{
return ;
} struct Node *p = NULL;
p = *head; *head = p->next;
int result = p->data; // 注意释放内存
free(p);
p = NULL; return result; } int deleteTailNode(struct Node **head);
int deleteTailNode(struct Node **head)
{
if (*head == NULL)
{
return ;
} struct Node *p,*q;
p = q = NULL;
p = *head;
q = p->next;
// 通过循环定位让q指向最后一个节点,p指向q前面一个节点
for (int i = ; i <= count(*head)-; i++)
{
p = q;
q = q->next;
}
// 取最后一个节点的数据
int result = q->data; p->next = NULL;
free(q);
q = NULL; return result;
} int main(int argc, const char * argv[])
{ struct Node *head = NULL;
// 产生链表
head = createLinkList(); // 输出链表元素个数
int c = count(head);
printf("c = %d\n",c); //insertIntoHead(&head, 10); //modifyNode(head, 2, 10); //insertIntoTail(&head, 100);
//insertInto(&head, 2, 100); //insertIntoSortedList(&head, 6);
//deleteFirstNode(&head);
int r = deleteTailNode(&head);
printf("删除最后一个节点%d\n",r); // 输出链表
printLinkList(head); /*
// 输出第二个节点的数据域;
c = getNode(head, 2);
printf("\n");
printf("c = %d\n",c);
*/ return ;
}
不才版
#include <stdio.h> #include <stdlib.h> struct Node
{
int data;
struct Node *next;
}; struct Node *creatLinkList(void)
{
struct Node *head=NULL;
struct Node *tail=NULL;
struct Node *temp=NULL; int data;
scanf("%d",&data);
while (data)
{
temp=malloc(sizeof(struct Node));
temp->data=data;
temp->next=NULL; if(head==NULL)
head=tail=temp;
else
{
tail->next=temp;
tail=temp;
}
scanf("%d",&data);
}
return head;
} void printLinkList(struct Node *head)
{
struct Node *tmp=head;
if (tmp==NULL) {
return;
}
while (tmp!=NULL) {
printf("%d->>",tmp->data);
tmp=tmp->next;
}
printf("\n");
} int toNode(struct Node *head,int pos)
{
int data;
for (int i=; i<pos; i++) {
if ((i!=pos-)&&(head->next==NULL))
return ;
data=head->data;
head=head->next;
}
return data; //链表长度可以用count(head)算出。
} int changeData(struct Node *head,int pos,int x)
{
for (int i=; i<pos; i++) {
if ((i!=pos-)&&(head->next==NULL))
return ;
if (i==pos-) {
head->data=x;
}
head=head->next;
}
return ;
} void insertNodeInHead(struct Node **head,int value)
{
struct Node *tmp=NULL;
tmp=(struct Node *)malloc(sizeof(struct Node));
tmp->data=value;
tmp->next=*head;
*head=tmp;
} void insertNodeInEnd(struct Node *head,int value)
{
struct Node *tmp=NULL;
tmp=(struct Node *)malloc(sizeof(struct Node));
tmp->data=value;
tmp->next=NULL;
if (head==NULL) {
head=tmp;
}
while (head->next!=NULL) {
head=head->next;
}
head->next=tmp;
} int insertData(struct Node *head,int pos,int value)
{
struct Node *tmp=NULL;
tmp=(struct Node *)malloc(sizeof(struct Node));
if (tmp==NULL) {
return ;
}
tmp->data=value;
if (pos==) {
return ;
}
for (int i=; i<pos; i++) { if ((i!=pos-)&&(head->next==NULL)) {
return ;
}
if (i==pos-) {
tmp->next=head->next;
head->next=tmp;
}
head=head->next;
}
return ;
} void insertSortData(struct Node *head,int value)
{
struct Node *tmp=(struct Node *)malloc(sizeof(struct Node));
tmp->data=value;
while (head->data<tmp->data) {
if (head->next->data>=tmp->data) {
tmp->next=head->next;
head->next=tmp;
return;
}
if (head->next==NULL) {
tmp->next=head->next;
head->next=tmp;
return;
}
head=head->next;
} } int deleteHead(struct Node **pointhead)
{
int data;
data=(*pointhead)->data;
struct Node *p=*pointhead;
*pointhead=(*pointhead)->next;
free(p);
p=NULL;
if (*pointhead==NULL||(*pointhead)->next==NULL) {
return ;
}
return data;
} int deleteEnd(struct Node *head)
{
struct Node *tmp=head;
int data;
if(head==NULL||head->next==NULL)
return ;
while (tmp->next!=NULL) {
if (tmp->next->next==NULL) {
data=tmp->next->data;
free(tmp->next);
tmp->next=NULL;
break;
}
tmp=tmp->next;
}
return data;
} int main(int argc,const char *argv[])
{
struct Node *h = creatLinkList();
printLinkList(h); //1、返回单链表中第pos个结点中的元素,若pos超出范围,则返回0
printf("%d\n",toNode(h,)); //2、把单链表中第pos个结点的值修改为x的值,若修改成功返回1,否则返回0
if (changeData(h,,)) {
printLinkList(h);
} //3、向单链表的表头插入一个元素
insertNodeInHead(&h, );
printLinkList(h); //4、向单链表的末尾添加一个元素
insertNodeInEnd(h, );
printLinkList(h); //5、向单链表中第pos个结点位置插入元素为x的结点,若插入成功返回1,否则返回0
if(insertData(h, , ))
printLinkList(h); //6、向有序单链表中插入元素x结点,使得插入后仍然有序
insertSortData(h, );
printLinkList(h); //7、从单链表中删除表头结点,并把该结点的值返回,若删除失败则返回0
printf("%d\n",deleteHead(&h));
printLinkList(h); //8、从单链表中删除表尾结点并返回它的值,若删除失败则返回0
printf("%d\n",deleteEnd(h));
printLinkList(h); return ;
}