求C语言大神解一下这道简单的链表题

2024-11-22 19:41:38
推荐回答(1个)
回答(1):

/*Description
给定一串数字,用链表结构进行存储。然后给定针对该链表的若干插入操作,要求将执行插入操作后的结果输出。

Input
第一行:输入一个整数n,表示这串数字有n个(n大于等于1)。
第二行:输入这n个整数。
第三行:输入一个整数m,表示需要执行m个插入操作。
后面m行:每行输入两个整数a和b,表示在这串数字的当前第a个数字之后插入数字b。(假设链表第一个节点编号为1)

Output
输出操作后的n+m个数字。每个数字用空格空开。

Sample Input
3
2 1 3
2
1 5
1 6

Sample Output
2 6 5 1 3

HINT
最后一个输出数字的后面没有空格
*/
#include
#include
#include

//节点结构
struct Node
{
int data; //数据
Node *next; //指向下一个节点
};

//创建链表头部,iData为数据
Node * CreateHead(int iData)
{
Node *pNode = new Node;
if (NULL == pNode) return NULL;
pNode->data = iData;
pNode->next = NULL;
return pNode;
}

//释放内存
void ClearList(Node *pHead)
{
Node *pNode = pHead;
while(NULL != pNode)
{
Node *pNext = pNode->next;
delete pNode;
pNode = pNext;
}
}

//打印链表数据
void PrintList(Node *pHead)
{
Node *pFindNode = pHead;

printf("\n-----------------链表数据打印--------------------\n");
while(NULL != pFindNode)
{
printf("%d\t", pFindNode->data);
pFindNode = pFindNode->next;
}
printf("\n----------------------END------------------------\n");
}

//插入节点函数,每次都返回链表头节点
Node *InsertData(int index, int data, int size, Node *pHead)
{
int i = 0;
Node *pFindNode = NULL;
Node *pNode = NULL;

//参数检查
if (NULL == pHead) return CreateHead(data);
if((index < 1) || (index > size)) return NULL;

//创建新节点
pNode = new Node;
if(NULL == pNode) return NULL;
pNode->data = data;
pNode->next = NULL;

//定位插入节点
pFindNode = pHead;
while(((index--) > 1) && (NULL != pFindNode->next))pFindNode = pFindNode->next;

//执行插入操作
Node *pNext = pFindNode->next;
pFindNode->next = pNode;
pNode->next = pNext;

return pHead;
}

int main(void)
{
int i = 0; //链表索引
int iData = 0; //节点存储数据
Node *pHead = NULL; //链表首部
int N = 0; //链表初始个数
int M = 0; //插入数据的个数
int size = 0; //链表的当前数据个数

//输入链表的初始元素个数
printf("请输入链表的容量(正整数>0):");
scanf("%d", &N);

//插入初始的数据
printf("请输入%d个整数(以空格分开):", N);
for(i = 0; i < N; ++i)
{
scanf("%d", &iData);
pHead = InsertData(i, iData, size, pHead); //开始插入节点,初次会创建头部
size++;//当前链表元素个数增1
}

//输入插入操作的次数
printf("请输入插入整数的个数(正整数>0):");
scanf("%d", &M);

//执行插入操作
while((M--) > 0)
{
printf("请输入一组插入操作(1<=index<=%d data):", N);
scanf("%d%d", &i,&iData);
pHead = InsertData(i, iData, size, pHead);
size++;
}

//打印数据
PrintList(pHead);

//清空内存
ClearList(pHead);
getch();
return 0;
}