求助一道C语言关于链表的问题，答对还有追加分数

2025-04-03 03:35:14

推荐回答（4个）

回答1：

struct _tagStudent
{
long lNo; //=========学号
char szName[20]; //==姓名
char cSex; //========性别
int nAge; //=========年龄
};

//定义Student结构
typedef struct _tagStudent Student;

struct _tagNode
{
struct _tagNode* pNext;//=======下一个节点
Student *pStudent; //===========本节点的学生信息
};

//定义Node结构（即一个节点）
typedef struct _tagNode Node;

//插入一个新的学生
//参数：
//Node* students 学生链表的头节点
//Student* newStudent 被插入的学生信息
//返回：
//新链表的头节点
Node* Insert(Node* students, Student* newStudent)
{
Node* pCurNode;//当前节点
Node* pNextNode;//下一节点
Node* pPrevNode;//上一节点
Node* pNode;

Node* pNodeHead = students;//头节点

if(pNodeHead == NULL)//尚未有节点，创建一个头节点
{
pNodeHead = (Node*)malloc(sizeof(Node));
pNodeHead->pNext = NULL; //后一项为NULL;
pNodeHead->pStudent = newStudent;

return pNodeHead;
}

pCurNode = pNodeHead;
pPrevNode = NULL;
while(1)
{
if(newStudent->lNo <= pNode->pStudent->lNo)//按学号升序插入,插到当前节点前
{
pNode = (Node*)malloc(sizeof(Node));
pNode->pStudent = newStudent;
pNode->pNext = pCurNode;

if(pPrevNode == NULL)//如果上一节点为NULL，表示插入链表头
pNodeHead = pNode;//链表头指向新节点
else
pPrevNode->pNext = pNode;
break;
}

pNextNode = pCurNode->pNext;

if(pNextNode == NULL)//如果当前节点是末节点,插入链表末尾
{
pNode = (Node*)malloc(sizeof(Node));
pNode->pStudent = newStudent;
pNode->pNext = NULL;

pCurNode->pNext = pNode;

break;
}

pPrevNode = pCurNode;
pCurNode = pNextNode;
}

return pNodeHead;//返回新的头节点
}

//在学生链表中查找指定的学生
//参数：
//Node* strudent 学生链表的头节点
//Student* searchStudent 被查找的学生
//返回：
//被查学生所在节点
Node* FindNode(Node* students, Student* searchStudent)
{
Node* pNode = students;

while(pNode != NULL)
{
if(pNode->pStudent == searchStudent)
return pNode;

pNode = pNode->pNext;
}

return NULL;
}

//根据学号查找学生信息
//参数：
//Node* students 学生链表的头节点
//long nNo 被查学生的学号
//返回：
//被查学生的信息
Student* FindStudent(Node* students, long lNo)
{
Node* pNode = students;

while(pNode != NULL)
{
if(pNode->pStudent->lNo == lNo)
return pNode->pStudent;

pNode = pNode->pNext;
}

return NULL;
}

//修改学生信息
//参数：
//Node* students 学生链表头节点
//Student* oldStudent 被修改的学生信息
//Student* newStudent 被修改后的学生信息(即用newStudent替换oldStudent)
//返回：
// true -- 成功，false -- 失败
bool Modify(Node* students, Student* oldStudent, Student* newStudent)
{
//查找被修改学生所在节点
Node* pNode = FindNode(students, oldStudent);

if(pNode == NULL)//没有找到返回false
return false;

//替换成新的学生信息
pNode->pStudent = newStudent;

return true;
}

//获取指定节点的上一个节点
//参数：
//Node* students 学生链表的头节点
//Node* pNode 指定节点
//返回：
//指定节点的上一个节点
Node* GetPrevNode(Node* students, Node* pNode)
{
Node* pCurNode = students;

if(pNode == students)//指定节点是头节点，返回上一节点NULL
return NULL;

while(pCurNode != NULL)
{
if(pNode == pCurNode->pNext)
return pCurNode;

pCurNode = pCurNode->pNext;
}

return NULL;//没有找到
}

//删除指定的学生信息
//参数：
//Node* students 学生链表头节点
//Student* pStudent 将被删除的学生
//返回：
//删除学生后的学生链表的头节点，如果为NULL，表示链表中已没有任何学生
Node* Delete(Node* students, Student* pStudent)
{
Node* pNodeHead = students;
Node* pPrevNode;//上一节点

//查找被修改学生所在节点
Node* pNode = FindNode(students, pStudent);

if(pNode == NULL)//没有找到返回原先的头节点
return pNodeHead;

if(pNode == pNodeHead)//如果该学生是头节点
{
pNodeHead = pNodeHead->pNext;
}
else
{
pPrevNode = GetPrevNode(students, pNode);

pPrevNode->pNext = pNode->pNext;
}

free(pNode);//释放该节点(没有释放节点中的学生信息，应另外释放)

return pNodeHead;//返回头节点
}

好了！以上已经有了基本的学生链表操作功能了。只要通过调用上面的几个函数就可以实现学生信息的管理和应用。

例如：
//参考样例====
//1。机器模拟生成20个学生，学号随机生成
//2。修改原学号为100的学生，替换为一个新的学号为150的学生
//3。删除学号为200的学生
void main()
{
int i = 0;
Node* students = NULL;//初始化学生链表头节点为空
Student* newStudent;
Student* oldStudent;
Node* pNode;

//1。机器模拟生成20个学生，学号随机生成

//随机产生20个学生，学号在0--1000之间，按照升序插入到学生链表中
for(i = 0; i < 20; i++)
{
newStudent = (Student*)malloc(sizeof(Student));
newStudent->lNo = rand() * 1000;//rand()为生成一个0到1的随机数，随机函数可以用别的替代，这里只是用于说明问题的

students = Insert(students, newStudent);
}

//遍历输出学生信息,用于检验学生链表是否正确，包括学生个数，学号是否排序正确等
i = 0;
pNode = students;
while(pNode != NULL)
{
printf("学生%d : 学号 -- %l\n", ++i, pNode->pStudent->lNo);
pNode = pNode->pNext;
}

//2。修改原学号为100的学生，替换为一个新的学号为150的学生
oldStudent = FindStudent(students, 100);

newStudent = (Student*)malloc(sizeof(Student));
newStudent->lNo = 150;

Modify(students, oldStudent, newStudent);

//3。删除学号为200的学生

//查找学号为200的学生
oldStudent = FindStudent(students, 200);

if(oldStudent != NULL)//如果找到
{
students = Delete(students, oldStudent);

free(oldStudent);//释放学生信息
}

//最后结束程序前，最好要把所有的学生信息释放掉
//。。。
}

回答2：

一个简单的带头尾指针单向链表（C实现）用C写了一个带头尾指针的单向链表，仅在尾部进行插入操作，在任意位置进行删除操作。因为只用到这么些功能，又因为懒，所以没有扩展。因为插入是固定在尾部进行，带一个尾指针的好处是显而易见的。当然删除时要付出一些开销。

list.h

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

/* list.h

*/

#ifndef LIST_H
#define LIST_H

#include
#include

struct listnode
{
struct listnode* next;
int data;
};

struct list
{
struct listnode* head;
struct listnode* tail;
int count;
};

void list_init(struct list*);
void list_insert(struct list*, struct listnode*);
int list_delete(struct list*, struct listnode*);

#endif

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

list.c

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

/* list.c
** Copyright 2004 Coon Xu.
** Author: Coon Xu
** Date: 06 Sep 2004
*/
#include "list.h"

void list_init(struct list* myroot)
{
myroot->count = 0;
myroot->head = NULL;
myroot->tail = NULL;
}

void list_insert(struct list* myroot, struct listnode* mylistnode)
{
myroot->count++;

mylistnode->next = NULL;
if(myroot->head == NULL)
{
myroot->head = mylistnode;
myroot->tail = mylistnode;
}
else
{
myroot->tail->next = mylistnode;
myroot->tail = mylistnode;
}
}

int list_delete(struct list* myroot, struct listnode* mylistnode)
{
struct listnode* p_listnode = myroot->head;
struct listnode* pre_listnode;

//myroot is empty
if(p_listnode == NULL)
{
return 0;
}

if(p_listnode == mylistnode)
{
myroot->count--;
//myroot has only one node
if(myroot->tail == mylistnode)
{
myroot->head = NULL;
myroot->tail = NULL;
}
else
{
myroot->head = p_listnode->next;
}
return 1;
}

while(p_listnode != mylistnode && p_listnode->next != NULL)
{
pre_listnode = p_listnode;
p_listnode = p_listnode->next;
}
if(p_listnode == mylistnode)
{
pre_listnode->next = p_listnode->next;
myroot->count--;
return 1;
}
else
{
return 0;
}

}

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

main.c

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

#include
#include
#include "list.h"

int main(int argc, char *argv[])
{
struct list l;
list_init(&l);
int ix = 0;

for(ix = 0; ix < 10; ix++)
{
struct listnode* p_node = malloc(sizeof(struct listnode));
p_node->data = ix;
list_insert(&l, p_node);
}

struct listnode* p_listnode = l.head;
while(p_listnode != NULL)
{
printf("%d\n", p_listnode->data);
p_listnode = p_listnode->next;
}

int input;
printf("input the number you want delete:\n");
scanf("%d", &input);

while(input > 0)
{
p_listnode = l.head;
while(p_listnode->next != NULL && p_listnode->data != input)
{
p_listnode = p_listnode->next;
}

if(p_listnode->data == input)
{
printf("Delete success!!\nprint the list!!\n");
list_delete(&l, p_listnode);
free(p_listnode);
p_listnode = l.head;
while(p_listnode != NULL)
{
printf("%d\n", p_listnode->data);
p_listnode = p_listnode->next;
}
}
else
{
printf("not find %d\n", input);
}
scanf("%d", &input);
}
system("PAUSE");
return 0;
}

回答3：

不明白你的含义，你问的问题是什么？提供一些这方面的东西给你

首先要确定一种排序算法，常用的几种有：

insert sort 插入排序

merge sort 归并排序

quick sort 快速排序

bubble sort 冒泡排序

heap sort 堆排序

radix sort 基数排序

算法性能的优劣取决于时间复杂度，一般来说，时间复杂度好的code编译起来较为麻烦，编译过程简单的算法时间复杂度相对较差.

insert sort 的时间复杂度较差，但是编译简单，也是最常用的一种排序算法，下面是C＋＋的inplementation(递归):

typedef struct node* LIST;

struct node {

int key;

node* next;

};

//需要一个插入函数

LIST _insert (LIST L, node* pNew)

{

if (L == NULL)

return pNew;

if (pNew->key < L->key)

{

pNew->next = L;

return pNew;

}

L->next = _insert (L->next, pNew);

return L;

}

LIST _insertsort (LIST L)

{

if (L == NULL) //空链，无须排序，返回.(递归的跳出条件）

return L;

node* tail = L->next;

L->next = NULL;

return _insert (_insertsort(tail), L);

}

回答4：

需要按照学号进行排序的!