函数题
6-6-1 求单链表的表长
实现一个函数，求带头结点的单链表的表长
接口：
int Length ( LinkList L );
其中LinkList结构定义如下：
typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList;
实现：
int Length ( LinkList L ) { int n = 0; LinkList cur = L; while(cur->next) { cur = cur->next; n++; } return n; }
6-6-2 求单链表元素序号
接口：
int Locate ( LinkList L, ElemType e);
L是带头结点的单链表的头指针，e是要查找的元素值。如果e在单链表中存在，函数Locate返回其序号（序号从1开始）；否则，返回0。
int Locate ( LinkList L, ElemType e) { int n = 1; LinkList cur = L->next; while(cur) { if(cur->data == e) return n; n++; cur = cur->next; } return 0; }
6-6-3 求单链表结点的阶乘和
本题要求实现一个函数，求单链表L结点的阶乘和。这里默认所有结点的值非负，且题目保证结果在int范围内。
接口：
int FactorialSum( List L );
其中单链表List的定义如下：
typedef struct Node *PtrToNode; struct Node { int Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */ }; typedef PtrToNode List; /* 定义单链表类型 */
实现：
int factorial(int data) { if (data == 0) return 1; else { int ret = data; while (--data) { ret *= data; } return ret; } } int FactorialSum( List L ) { if(L==NULL) return 0; int ret = 0; List cur = L; while(cur) { ret += factorial(cur->Data); cur = cur->Next; } return ret; }
6-6-4 逆序数据建立链表
实现一个函数，按输入数据的逆序建立一个链表。
接口：
struct ListNode *createlist();
函数createlist利用scanf从输入中获取一系列正整数，当读到−1时表示输入结束。按输入数据的逆序建立一个链表，并返回链表头指针。链表节点结构定义如下：
struct ListNode { int data; struct ListNode *next; };
可以直接头插，这里为了多写一个反转链表，特意搞了尾插再反转
实现：
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newhead = NULL, * cur = head; while (cur) { struct ListNode* next = cur->next; cur->next = newhead; newhead = cur; cur = next; } return newhead; } struct ListNode* BuySLTNode(int x) { struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; return newnode; } void SLTPushBack(struct ListNode** pphead, int x) { struct ListNode* newnode = BuySLTNode(x); if (*pphead == NULL) { *pphead = newnode; } else { struct ListNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } struct ListNode* createlist() { struct ListNode* head = NULL; int n = 0; while (1) { scanf("%d", &n); if (n == -1) break; SLTPushBack(&head, n); } struct ListNode* ret = reverseList(head); return ret; }
编程题
6-7-1 单链表的创建及遍历
#include<stdio.h> #include<stdlib.h> typedef struct ListNode { int data; struct ListNode* next; }ListNode; ListNode* BuySLTNode(int x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; return newnode; } void SLTPushBack(ListNode** pphead, int x) { ListNode* newnode = BuySLTNode(x); if (*pphead == NULL) { *pphead = newnode; } else { ListNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } int main() { int n = 0; scanf("%d", &n); if(n == 0) return 0; ListNode* head = NULL; while (n--) { int c = 0; scanf("%d", &c); SLTPushBack(&head, c); } ListNode* cur = head; printf("%d", cur->data); cur = cur->next; while (cur) { printf(" %d", cur->data); cur = cur->next; } return 0; }
