C++ 实现带头结点单链表基本操作：求表长、定位和插入

#include using namespace std;

typedef int ElemType; // 假设链表存储的数据类型为整数

// 定义链表结点结构体 typedef struct LNode{ ElemType data; // 数据域 struct LNode *next; // 指针域，指向下一个结点 }LNode, *LinkList;

// 创建带头结点的单链表 LinkList createList(int n){ LinkList L; L = new LNode; // 创建头结点 L->next = NULL; // 头结点的指针域为空

// 依次插入n个结点
LNode *p;
for(int i=0; i<n; i++){
    p = new LNode;
    cin >> p->data;
    p->next = L->next;  // 将新结点插入到头结点之后
    L->next = p;
}

return L;

}

// 求表长 int ListLength(LinkList L){ int len = 0; LNode *p = L->next; // 从第一个结点开始计数 while(p != NULL){ len++; p = p->next; } return len; }

// 定位元素 int LocateElem(LinkList L, ElemType e){ int pos = 0; LNode *p = L->next; while(p != NULL){ pos++; if(p->data == e){ return pos; } p = p->next; } return 0; }

// 插入元素 bool ListInsert(LinkList &L, int i, ElemType e){ if(i < 1 || i > ListLength(L)+1){ // 判断插入位置是否合法 return false; } LNode *p = L; int j = 0; while(p != NULL && j < i-1){ // 找到第i-1个结点 p = p->next; j++; } LNode *newNode = new LNode; // 创建新结点 newNode->data = e; newNode->next = p->next; // 将新结点插入到第i个结点之前 p->next = newNode;

return true;

}

int main(){ int n; cout << "请输入链表长度："; cin >> n; LinkList L = createList(n);

cout << "链表的长度为：" << ListLength(L) << endl;

ElemType e;
cout << "请输入要查找的元素：";
cin >> e;
int pos = LocateElem(L, e);
if(pos == 0){
    cout << "该元素在链表中不存在" << endl;
}
else{
    cout << "该元素在链表中的位置为：" << pos << endl;
}

int i;
cout << "请输入要插入的位置：";
cin >> i;
cout << "请输入要插入的元素：";
cin >> e;
if(ListInsert(L, i, e)){
    cout << "插入成功" << endl;
    cout << "插入后的链表为：";
    LNode *p = L->next;
    while(p != NULL){
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}
else{
    cout << "插入失败，位置不合法" << endl;
}

return 0;

}