8 查找序列元素（链表）
作者: Turbo时间限制: 1S章节: DS:数组和链表
问题描述 :
使用带头结点的单链表编程：
一群学生排成一行，输入一个学号，请确定该学号学生所在的位置。
输入说明 :
第一行输入学生信息：
第一个整数n(0<=n<=100)，表示共有n个学生，其后有n个整数，表示n个学生的学号
第二行及以后各行，每行输入一个整数，表示要查找的学生学号。
输出说明 :
对于每个要查找的学号，输出一个整数，表示要查找学生的位置。如果共有n个学生，则位置序号为1~n。
如果学生不存在，输出“no”，不包括双引号。
每个输出占一行。
// LNode.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include <iostream> using namespace std; class LNode { public: int data; LNode* next; }; class LinkList { //既要考虑len，又要考虑position //对链表操作后，要考虑len的增减 public: int len; LinkList();//默认构造函数 LinkList(int llen); ~LinkList();//解析函数,主动释放空间 void pri_all(); int search(int stu_num);//返还position,stu_num不存在，则返回'-1' bool insert(int position, int stu_num); bool del(int position); bool intersection(LinkList b, LinkList& result);//求交集 bool intersection_order(LinkList b, LinkList& result);//求有序链表交集 private: LNode* head;//头指针 }; int main() { int len_a; cin >> len_a; LinkList stu_a(len_a); int len_b; cin >> len_b; LinkList stu_b(len_b); LinkList result; stu_a.intersection_order(stu_b, result); result.pri_all(); return 0; } inline LinkList::LinkList() { len = 0; this->head = new LNode; this->head->data = 0; this->head->next = NULL; } LinkList::LinkList(int llen) { len = llen; this->head = new LNode; this->head->data = 0; this->head->next = NULL; LNode* now = head; for (int i = 1; i <= len; i++) { LNode* temp = new LNode;//即使是此次循环再一次创建temp，上一次循环temp指向的空间依旧存在 cin >> temp->data; now->next = temp; now = temp; } now->next = NULL; } inline LinkList::~LinkList() { //从前往后释放空间 LNode* temp; while (head->next != NULL) { temp = head->next; delete head; head = temp; } delete head;//delete：作用对象是指针，释放指针指向的空间 len = 0; } void LinkList::pri_all() { if (len == 0) { cout << "head-->tail" << endl; return; } LNode* now = head;//头节点 cout << "head-->"; while (now->next != NULL) {// now = now->next; cout << now->data << "-->"; } cout << "tail" << endl; /*存在问题，链表中没有储存数据，此时now就是NULL，而now->next已经越界 while (now->next != NULL) {//循环到（不检查）尾节点时，跳出 cout << now->data << "-->"; now = now->next; } cout << now->data << "-->tail" << endl;*/ } int LinkList::search(int stu_num) { int position = 0; LNode* now = head->next;//从首元节点开始 while (now != NULL && now->data != stu_num) {//检查完尾节点，跳出 position++; now = now->next; } position++;//now->data == stu_num时，跳出循环，少了一次position++ if (now != NULL) { return position; } else { cout << "no" << endl; return -1; } } bool LinkList::insert(int position, int stu_num) { if (position<1 || position>len + 1) { return false; } int p_now = 0; LNode* now = head; while (p_now != position - 1) { now = now->next; p_now++; } LNode* temp = new LNode; temp->data = stu_num; temp->next = now->next; now->next = temp; len++; return true; } bool LinkList::del(int position) { if (position<1 || position>len|| len==0) { return false; } //从头节点开始处理，就不需要单独考虑链头，链尾的 LNode* now = head; for (int i = 1; i <= position - 1; i++) {//要使循环停止时，now在要删除元素的前一位 now = now->next; } LNode* temp = now->next; now->next = now->next->next; delete temp; len--; return ture; /* LNOde* now=head; int p_now = 0; //p_now!=position,是对当下的判断，而now->next!=NULL,是对下一步是否能进行的判断 while(p_now!=position-1 && now->next!=NULL){ now = now->next; p_now++; } //排除了position=1但len=0(此时p_now!=position第一次就判断失败，跳过循环，但是len=0意味delete操作时无效的)和positio越界的问题 if(now->next==NULL) return false; LNode* temp = now->next; now->next = now->next->next; delete temp; len--; return ture;*/ } bool LinkList::intersection(LinkList b, LinkList& result) { LNode* now_a = head->next;//首元节点 while (now_a != NULL) { LNode* now_b = b.head->next;//首元节点 while (now_b != NULL) { if (now_a->data == now_b->data) { result.insert(result.len + 1, now_a->data); break; } now_b = now_b->next; } now_a = now_a->next; } if (result.len == 0) { return false; } else { return true; } } bool LinkList::intersection_order(LinkList b, LinkList& result) { LNode* now_a = head->next;//首元节点 LNode* begin_b = b.head->next;//首元节点 while (now_a != NULL) { LNode* now_b = begin_b; while (now_b != NULL) { if (now_a->data == now_b->data) { result.insert(result.len + 1, now_a->data); if (now_b->next != NULL) { begin_b = now_b->next; } else { begin_b = now_b; } break; } now_b = now_b->next; } now_a = now_a->next; } if (result.len == 0) { return false; } else { return true; } }